Czy dobrze napisałem kod na podstawie polecenia? Problem plecakowy

0

Witam. Dostałem takie zadanie do zrobienia:

  1. Etap I programowania dynamicznego. Napisz program będący implementacją programowania
    dynamicznego dla problemu plecakowego. Jako struktury danych użyj tablicy
    wszystkich rozwiązań P oraz tablicy umożliwiającej odczytywanie rozwiązań Q.
    Etap II programowania dynamicznego. Napisz program, który danej liczby rzeczy
    i pojemności plecaka będzie odczytywał rozwiązanie z tablic utworzonych w Etapie I.

Jakby były jakieś błędy, pomógłby ktoś w poprawieniu kodu?

#include <iostream>

using namespace std;

int main()
{
    int i, j, ilosc, pojemnosc;

    cout << "Podaj liczbe przedmiotow : ";
    cin >> ilosc;
    cout << "Podaj pojemnosc plecaka : ";
    cin >> pojemnosc;
    cout << endl;

    int * m = new int[ ilosc ];
    int * c = new int[ ilosc ];

    int ** Q = new int *[ ilosc + 1 ];

    for( i = 0; i <= ilosc; ++i )
         Q[ i ] = new int[ pojemnosc + 1 ];

    int ** P = new int *[ ilosc + 1 ];

    for( i = 0; i <= ilosc; ++i )
         P[ i ] = new int[ pojemnosc + 1 ];

    for( i = 0; i < ilosc; ++i )
    {
        cout << "Podaj wartosc przedmiotu : ";
        cin >> c[ i ];
        cout << "Podaj wage przedmiotu : ";
        cin >> m[ i ];
        cout << endl;
    }

    for( i = 0; i <= ilosc; ++i ) {
        P[ i ][ 0 ] = 0;
        Q[ i ][ 0 ] = 0;
    }

    for( j = 0; j <= pojemnosc; ++j ) {
        P[ 0 ][ j ] = 0;
        Q[ 0 ][ j ] = 0;
    }

    for( i = 1; i <= ilosc; ++i ) {
        for( j = 1; j <= pojemnosc; ++j ) {
            if(( j >= m[ i - 1 ] ) &&( P[ i - 1 ][ j ] <( P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ] ) ) ) {
                P[ i ][ j ] = P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ];
                Q[ i ][ j ] = i;
            }
            else {
                P[ i ][ j ] = P[ i - 1 ][ j ];
                Q[ i ][ j ] = Q[ i - 1 ][ j ];
            }
        }
    }

    cout << " Wypisanie tablicy P " << endl;

    for( i = 1; i <= ilosc; ++i )
    {
        for( j = 1; j <= pojemnosc; ++j )
        {
            cout << P[ i ][ j ] << " ";
        }
        cout << endl;
    }
    cout << "Wynik : " << P[ ilosc ][ pojemnosc ] << endl;

    return 0;
}
1

1.: Nazewnictwo zmiennych! Będzie łatwiej Tobie i innym, którzy będą czytać ten kod. Nazywaj zmienne tym, czym są -> Jeśli zmienna przechowuje przykładowo wielkość plecaka, to nazwij ją backpackSize.

2.: Wielokrotnie wykraczasz poza obszar tablic:
for( i = 1; i <= ilosc; ++i ) <- Zaczynasz od numeru jeden, pomijając pierwszy element tablicy, na koniec próbujesz odwołać się do elementu o numerze ilosc, podczas gdy tablica ma przecież rozmiar ilosc - 1. Deklaracja i korzystanie z tablic, to coś z czym musisz się bardziej zapoznać, bo póki co generujesz błedy w swoim kodzie.

edit: Widzę, że rozmiar tablicy jest ilosc + 1, ale to nawet jeszcze gorzej, bo nie daje Tobie nic (wciąż omijasz pierwszy element tablicy), a dodatkowo komplikujesz zapis. Dlaczego nie po prostu: plecak[ ilosc ]?

3.: Tego fragmentu nawet nie będę komentował:

if(( j >= m[ i - 1 ] ) &&( P[ i - 1 ][ j ] <( P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ] ) ) ) {
                P[ i ][ j ] = P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ];
                Q[ i ][ j ] = i;
            }

Nie wiem co próbowałeś tu zrobić, ale zanim bym do tego doszedł dostałbym oczopląsu i bólu głowy. Na pewno da się zapisać to lepiej.
Takie potwory możesz rozbić na kolejne operacje, przypisać fragmenty do pomocniczych zmiennych, kombinuj. Unikaj takich zapisów!

4.: Pamięci wyciekło Ci tyle, że prawdopodobnie kapie nawet do sąsiada...
Używaj delete na każdym wskaźniku, który alokujesz za pomocą new, jeśli jednak sobie z tym nie radzisz - to używaj kontenerów, na przykład vector'a

0

To jest piękne!

 for( i = 1; i <= ilosc; ++i ) {
        for( j = 1; j <= pojemnosc; ++j ) {
            if(( j >= m[ i - 1 ] ) &&( P[ i - 1 ][ j ] <( P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ] ) ) ) {
                P[ i ][ j ] = P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ];
                Q[ i ][ j ] = i;
            }
            else {
                P[ i ][ j ] = P[ i - 1 ][ j ];
                Q[ i ][ j ] = Q[ i - 1 ][ j ];
            }
        }
    }
0

Przerobiłem kod na funkcje. Przy wpisywaniu wagi wywala mi program. O co chodzi?


#include <iostream>
#include <string>

void PobierzDaneGlowne( int & ilosc, int & pojemnosc );
void UtworzTablice( int  ilosc, int  pojemnosc );
void PrzypiszWartoscidoTablic( int ilosc, int pojemnosc, int * m, int * c, int ** P, int ** Q );
void AlgorytmPlecakowy( int ilosc, int pojemnosc, int * m, int * c, int ** P, int ** Q );
void WypiszTabliceWynikow( int ilosc, int pojemnosc, int ** tab );
void WypiszWyniki( int ** P, int ** Q, int * m, int * c, int ilosc, int pojemnosc );

using namespace std;

int main()
{
    int pojemnosc, ilosc;
    int * m, * c;
    int ** P, ** Q;

    PobierzDaneGlowne( ilosc, pojemnosc );
    UtworzTablice( ilosc, pojemnosc );
    PrzypiszWartoscidoTablic( ilosc, pojemnosc, m, c, P, Q );
    AlgorytmPlecakowy( ilosc, pojemnosc, m, c, P, Q );
    WypiszTabliceWynikow( ilosc, pojemnosc, P );
    WypiszTabliceWynikow( ilosc, pojemnosc, Q );
    WypiszWyniki( P, Q, m, c, ilosc, pojemnosc );



    return 0;
}

void PobierzDaneGlowne( int & ilosc, int & pojemnosc )
{
    cout << "Podaj pojemnosc plecaka : ";
    cin >> pojemnosc;
    cout << "Podaj liczbe przedmiotow : ";
    cin >> ilosc;
    cout << endl;
}

void UtworzTablice( int ilosc, int pojemnosc )
{
    int i;

    int * m = new int[ ilosc ];
    int * c = new int[ ilosc ];

    int ** Q = new int *[ ilosc + 1 ];

    for( i = 0; i <= ilosc; ++i )
         Q[ i ] = new int[ pojemnosc + 1 ];

    int ** P = new int *[ ilosc + 1 ];

    for( i = 0; i <= ilosc; ++i )
         P[ i ] = new int[ pojemnosc + 1 ];

}

void PrzypiszWartoscidoTablic( int ilosc, int pojemnosc, int * m, int * c, int ** P, int ** Q )
{
    int i, j;
    for( int i = 0; i < ilosc; ++i )
    {

        cout << "Podaj wage przedmiotu : ";
        cin >> m[ i ];
        cout << "Podaj wartosc przedmiotu : ";
        cin >> c[ i ];
        cout << endl;
    };

    for( i = 0; i <= ilosc; ++i ) {
        P[ i ][ 0 ] = 0;
        Q[ i ][ 0 ] = 0;
    };

    for( j = 0; j <= pojemnosc; ++j ) {
        P[ 0 ][ j ] = 0;
        Q[ 0 ][ j ] = 0;
    };
}

void AlgorytmPlecakowy( int ilosc, int pojemnosc, int * m, int * c, int ** P, int ** Q )
{
    int i, j;

    for( i = 1; i <= ilosc; ++i ) {
        for( j = 1; j <= pojemnosc; ++j ) {
            if(( j >= m[ i - 1 ] ) &&( P[ i - 1 ][ j ] <( P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ] ) ) ) {
                P[ i ][ j ] = P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ];
                Q[ i ][ j ] = i;
            }
            else {
                P[ i ][ j ] = P[ i - 1 ][ j ];
                Q[ i ][ j ] = Q[ i - 1 ][ j ];
            }
        }
    };
}

void WypiszTabliceWynikow( int ilosc, int pojemnosc, int ** tab )
{
    int i, j;
    cout << " Tablica : " << endl;

    for( i = 1; i <= ilosc; ++i )
    {
        for( j = 1; j <= pojemnosc; ++j )
        {
            cout << tab[ i ][ j ] << " ";
        };
        cout << endl;
    };
}

void WypiszWyniki( int ** P, int ** Q, int * m, int * c, int ilosc, int pojemnosc )
{
    cout << endl;
    cout << "MAX : " << P[ ilosc ][ pojemnosc ] << endl; // Wartosc najlepszej opcji pakunku.


}
1

Nigdy nie ustawiasz wartości lokalnych zmiennych m oraz c zadeklarowanych w funkcji main.
To, że w innej funkcji sobie nazwałeś te zmienne tak samo, nie ma żadnego znaczenia.

1

W tym momencie:

int * m, * c;

tworzysz dwa wskaźniki, które wskazują na losowe miejsce w pamięci, albo na zero, co również nie jest prawidłowe.
Nie alokujesz pamięci, a potem nieprawidłowy wskaźnik wrzucasz tutaj:

PrzypiszWartoscidoTablic( ilosc, pojemnosc, m, c, P, Q );

w której to funkcji próbujesz wpisać do tego wskaźnika jakąś wartość...

Zaalokuj pamięć, na którą wskazuje ten wskaźnik, lub użyj vector'a, tak jak pisałem wcześniej.

0

Czyli jak mam to poprawić? Nie za bardzo rozumiem.

1

Zainspiruj się tym, jak przekazujesz pojemnosc oraz ilosc :-)

0

a mógłbyś dać przykład z jednej z moich funkcji, bo dalej nie mogę dojść do rozwiazania problemu, caly czas mi bledy wyskakuja :/

0 
#include <iostream>
#include <string>

void PobierzDaneGlowne( int & ilosc, int & pojemnosc );
void UtworzTablice( int  ilosc, int  pojemnosc );
void PrzypiszWartoscidoTablic( int ilosc, int pojemnosc, int * m, int * c, int ** P, int ** Q );
void AlgorytmPlecakowy( int ilosc, int pojemnosc, int * m, int * c, int ** P, int ** Q );
void WypiszTabliceWynikow( int ilosc, int pojemnosc, int ** tab );
void WypiszWyniki( int ** P, int ** Q, int * m, int * c, int ilosc, int pojemnosc );

using namespace std;

int main()
{
    int pojemnosc, ilosc;

    int * m = new int[ ilosc ];
    int * c = new int[ ilosc ];
    int ** Q = new int *[ ilosc + 1 ];
    int ** P = new int *[ ilosc + 1 ];


    PobierzDaneGlowne( ilosc, pojemnosc );
    UtworzTablice( ilosc, pojemnosc );
    PrzypiszWartoscidoTablic( ilosc, pojemnosc, m, c, P, Q );
    AlgorytmPlecakowy( ilosc, pojemnosc, m, c, P, Q );
    WypiszTabliceWynikow( ilosc, pojemnosc, P );
    WypiszTabliceWynikow( ilosc, pojemnosc, Q );
    WypiszWyniki( P, Q, m, c, ilosc, pojemnosc );

    return 0;
}

void PobierzDaneGlowne( int & ilosc, int & pojemnosc )
{
    cout << "Podaj pojemnosc plecaka : ";
    cin >> pojemnosc;
    cout << "Podaj liczbe przedmiotow : ";
    cin >> ilosc;
    cout << endl;
}

void UtworzTablice( int ilosc, int pojemnosc )
{
    int i;

    int * m = new int[ ilosc ];
    int * c = new int[ ilosc ];

    int ** Q = new int *[ ilosc + 1 ];

    for( i = 0; i <= ilosc; ++i )
         Q[ i ] = new int[ pojemnosc + 1 ];

    int ** P = new int *[ ilosc + 1 ];

    for( i = 0; i <= ilosc; ++i )
         P[ i ] = new int[ pojemnosc + 1 ];

}

void PrzypiszWartoscidoTablic( int ilosc, int pojemnosc, int * m, int * c, int ** P, int ** Q )
{
    int i, j;
    for( int i = 0; i < ilosc; ++i )
    {

        cout << "Podaj wage przedmiotu : ";
        cin >> m[ i ];
        cout << "Podaj wartosc przedmiotu : ";
        cin >> c[ i ];
        cout << endl;
    };

    for( i = 0; i <= ilosc; ++i ) {
        P[ i ][ 0 ] = 0;
        Q[ i ][ 0 ] = 0;
    };

    for( j = 0; j <= pojemnosc; ++j ) {
        P[ 0 ][ j ] = 0;
        Q[ 0 ][ j ] = 0;
    };
}

void AlgorytmPlecakowy( int ilosc, int pojemnosc, int * m, int * c, int ** P, int ** Q )
{
    int i, j;

    for( i = 1; i <= ilosc; ++i ) {
        for( j = 1; j <= pojemnosc; ++j ) {
            if(( j >= m[ i - 1 ] ) &&( P[ i - 1 ][ j ] <( P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ] ) ) ) {
                P[ i ][ j ] = P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ];
                Q[ i ][ j ] = i;
            }
            else {
                P[ i ][ j ] = P[ i - 1 ][ j ];
                Q[ i ][ j ] = Q[ i - 1 ][ j ];
            }
        }
    };
}

void WypiszTabliceWynikow( int ilosc, int pojemnosc, int ** tab )
{
    int i, j;
    cout << " Tablica : " << endl;

    for( i = 1; i <= ilosc; ++i )
    {
        for( j = 1; j <= pojemnosc; ++j )
        {
            cout << tab[ i ][ j ] << " ";
        };
        cout << endl;
    };
}

void WypiszWyniki( int ** P, int ** Q, int * m, int * c, int ilosc, int pojemnosc )
{
    cout << endl;
    cout << "MAX : " << P[ ilosc ][ pojemnosc ] << endl; // Wartosc najlepszej opcji pakunku.

}

wszystko juz mogę wpisać. teraz wywala mi podczas kiedy ma wyswietlić mi tablicę i wynik

1 
int pojemnosc, ilosc;
 
int * m = new int[ ilosc ]; // w tym miejscu następuje inicjalizacja zmiennej "m" - jak Ci się wydaje, ile wynosi "ilość" w *dokładnie tym* miejscu?

Rzuć okiem na jakiś poradnik o referencjach w C++, zamiast zgadywać jak powinno to wyglądać ;-)

0

a mógłbyś mi pomóc to poprawić, żebym wiedział na przyszłość gdzie popełniam błędy? bo co zmienię, to dalej wywala program :/

1

Porównaj obydwa te kody i pomyśl, jak możesz tę różnicę wykorzystać w swojej aplikacji:

https://ideone.com/yTlPQR
https://ideone.com/O7L0uB

0

Próbuje tak i dalej wywala :/

#include <iostream>
#include <string>

void PobierzDaneGlowne( int & ilosc, int & pojemnosc );
void UtworzTablice( int & ilosc, int & pojemnosc );
void PrzypiszWartoscidoTablic( int & ilosc, int & pojemnosc, int *& m, int *& c, int ** P, int ** Q );
void AlgorytmPlecakowy( int & ilosc, int & pojemnosc, int *& m, int *& c, int ** P, int ** Q );
void WypiszTabliceWynikow( int & ilosc, int & pojemnosc, int ** tab );
void WypiszWyniki( int ** P, int ** Q, int *& m, int *& c, int & ilosc, int & pojemnosc );

using namespace std;

int main()
{
    int pojemnosc, ilosc;

    int * m = new int[ ilosc ];
    int * c = new int[ ilosc ];
    int ** Q = new int *[ ilosc + 1 ];
    int ** P = new int *[ ilosc + 1 ];


    PobierzDaneGlowne( ilosc, pojemnosc );
    UtworzTablice( ilosc, pojemnosc );
    PrzypiszWartoscidoTablic( ilosc, pojemnosc, m, c, P, Q );
    AlgorytmPlecakowy( ilosc, pojemnosc, m, c, P, Q );
    WypiszTabliceWynikow( ilosc, pojemnosc, P );
    WypiszTabliceWynikow( ilosc, pojemnosc, Q );
    WypiszWyniki( P, Q, m, c, ilosc, pojemnosc );

    delete[] m;
    delete[] c;
    delete[] Q;
    delete[] P;

    return 0;
}

void PobierzDaneGlowne( int & ilosc, int & pojemnosc )
{
    cout << "Podaj pojemnosc plecaka : ";
    cin >> pojemnosc;
    cout << "Podaj liczbe przedmiotow : ";
    cin >> ilosc;
    cout << endl;
}

void UtworzTablice( int & ilosc, int & pojemnosc )
{
    int i;

    int * m = new int[ ilosc ];
    int * c = new int[ ilosc ];

    int ** Q = new int *[ ilosc + 1 ];

    for( i = 0; i <= ilosc; ++i )
         Q[ i ] = new int[ pojemnosc + 1 ];

    int ** P = new int *[ ilosc + 1 ];

    for( i = 0; i <= ilosc; ++i )
         P[ i ] = new int[ pojemnosc + 1 ];

}

void PrzypiszWartoscidoTablic( int & ilosc, int & pojemnosc, int *& m, int *& c, int ** P, int ** Q )
{
    int i, j;
    for( int i = 0; i < ilosc; ++i )
    {

        cout << "Podaj wage przedmiotu : ";
        cin >> m[ i ];
        cout << "Podaj wartosc przedmiotu : ";
        cin >> c[ i ];
        cout << endl;
    };

    for( i = 0; i <= ilosc; ++i ) {
        P[ i ][ 0 ] = 0;
        Q[ i ][ 0 ] = 0;
    };

    for( j = 0; j <= pojemnosc; ++j ) {
        P[ 0 ][ j ] = 0;
        Q[ 0 ][ j ] = 0;
    };
}

void AlgorytmPlecakowy( int & ilosc, int & pojemnosc, int *& m, int *& c, int ** P, int ** Q )
{
    int i, j;

    for( i = 1; i <= ilosc; ++i ) {
        for( j = 1; j <= pojemnosc; ++j ) {
            if(( j >= m[ i - 1 ] ) &&( P[ i - 1 ][ j ] <( P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ] ) ) ) {
                P[ i ][ j ] = P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ];
                Q[ i ][ j ] = i;
            }
            else {
                P[ i ][ j ] = P[ i - 1 ][ j ];
                Q[ i ][ j ] = Q[ i - 1 ][ j ];
            }
        }
    };
}

void WypiszTabliceWynikow( int & ilosc, int & pojemnosc, int ** tab )
{
    int i, j;
    cout << " Tablica : " << endl;

    for( i = 1; i <= ilosc; ++i )
    {
        for( j = 1; j <= pojemnosc; ++j )
        {
            cout << tab[ i ][ j ] << " ";
        };
        cout << endl;
    };
}

void WypiszWyniki( int ** P, int ** Q, int *& m, int *& c, int & ilosc, int & pojemnosc )
{
    cout << endl;
    cout << "MAX : " << P[ ilosc ][ pojemnosc ] << endl; // Wartosc najlepszej opcji pakunku.

}
3

Wyobraż sobie, że jesteś komputerem i idziesz linijka po linijce po swoim kodzie:

int pojemnosc, ilosc; // utwórz zmienne "pojemność" oraz "ilość" o nieoznaczonych (!) wartościach
 
int * m = new int[ ilosc ]; // utwórz zmienną "m" i przypisz do niej tablicę o rozmiarze... no właśnie, jakim?

1 użytkowników online, w tym zalogowanych: 0, gości: 1