Dynamiczne programowanie problem plecakowy

Odpowiedz Nowy wątek
2018-11-20 19:31

Rejestracja: 1 rok temu

Ostatnio: 4 dni temu

0

Witam,
Pomógłby ktoś znaleźć błąd w tym programie (Dyskretny problem plecakowy-programowanie dynamiczne).
Problem polega na tym że dla n>10 program nie działa(przestaje działać).
funkcja rekurenacyjna "wypisz_wynik" wypisuje indeksy przedmiotów w rozwiązaniu optymalnym.

dla danych wejściowych z pliku, program się zawiesza:

10 6
1 1
5 2
5 4
3 5
9 6
4 4
4 4
3 6
5 5
4 1

gdzie w pierwszej lini, po lewej stronie-ilość przedmiotów, po prawej ładowność plecaka.
w kolejnych liniach przedmioty. lewa-cena, prawa-waga.

Kod programu:

#include <iostream>
#include <fstream>

using namespace std;

class przedmiot{
    private:
    int waga;
    int cena;
    public:
    int getWaga(){
        return waga;
    }
    int getCena(){
        return cena;
    }
    int setWaga(int wg){
        waga=wg;
    }
    int setCena(int cn){
        cena=cn;
    }

};
void wypisz_wynik(int** s, int n, int W, przedmiot p[]){

    if(n==0 || W==0){
            cout<<endl;
        return;
    }
    if(s[n][W]==s[n-1][W] && s[n][W]!=(s[n-1][W-p[n-1].getWaga()])+p[n-1].getCena()){
        wypisz_wynik(s,n-1,W,p);
    }

    if(s[n][W]==s[n-1][W] && s[n][W]==(s[n-1][W-p[n-1].getWaga()])+p[n-1].getCena()){
        cout<<n<<" ";
        wypisz_wynik(s,n-1,W-p[n-1].getWaga(),p);
    }
    if(s[n][W]==s[n-1][W] && s[n][W]==(s[n-1][W-p[n-1].getWaga()])+p[n-1].getCena()){
        wypisz_wynik(s,n-1,W,p);
    }

    if(s[n][W]!=s[n-1][W] && s[n][W]==(s[n-1][W-p[n-1].getWaga()])+p[n-1].getCena()){
        cout<<n<<" ";
        wypisz_wynik(s,n-1,W-p[n-1].getWaga(),p);
    }

}

int main()
{
    fstream wej;
    fstream wyj;
    wej.open("In0302.txt",ios::in);
    wyj.open("Out0302.txt",ios::out);
    int n;
    int pom;
    int W; //rozmiar pleceaka
    wej>>n;
    wej>>W;
    przedmiot Przedmioty[n];
    for(int i=0;i<n;i++){
        wej>>pom;
        Przedmioty[i].setCena(pom);
        wej>>pom;
        Przedmioty[i].setWaga(pom);
    }

// algorytm zagadnienia plecakowego

 n++;
    W++;
    int **s= new int *[W];
    for(int i=0;i<n;i++){
        s[i]= new int[W];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<W;j++){
            if(i==0 || j==0){
                s[i][j]=0;
                continue;
            }
            if(Przedmioty[i-1].getWaga()>j){
                s[i][j]=s[i-1][j];
                continue;
            }
            s[i][j]=max(s[i-1][j-Przedmioty[i-1].getWaga()]+Przedmioty[i-1].getCena(),s[i-1][j]);
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<W;j++){
            cout<<s[i][j]<<" ";
        }
        cout<<endl;
    }
   wypisz_wynik(s,n-1,W-1,Przedmioty);

    return 0;
}

Jeśli czegoś nie napisałem, to proszę pytać.
Kto pomoże?

edytowany 2x, ostatnio: kq, 2018-11-21 01:29
Taguj wątki nazwami języków/technologii, nie bzdurami w stylu programowanie. - furious programming 2018-11-20 19:50
zmień też tytuł, np na: "Dynamiczne programowanie problem plecakowy", bo ten obecny jest nic nie znaczącą watą słowną. - MarekR22 2018-11-20 21:28

Pozostało 580 znaków

2018-11-20 20:17

Rejestracja: 3 lata temu

Ostatnio: 1 godzina temu

1
spamgolden napisał(a):
 n++;
    W++;
    int **s= new int *[W];
    for(int i=0;i<n;i++){
        s[i]= new int[W];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<W;j++){

Rezerwujesz W tablic o rozmiarze W, a potem indeksujesz do n. To może być problem.

edytowany 1x, ostatnio: furious programming, 2018-11-20 20:23
Pokaż pozostałe 5 komentarzy
Mam rację do końca bo próbujesz się dostać do niezaalokowanej pamięci, co jest błędem, który po prostu nie zawsze musi mieć dla ciebie złe konsekwencje. To jest UB. - GutekSan 2018-11-20 20:34
a wiesz może jak naprawić to? bo w tym programie często będzie zdarzała sie sytuacja że n<W - spamgolden 2018-11-20 20:35
No pomyśl... - GutekSan 2018-11-20 20:36
zwiększyć indeksowanie? i indeksować do W+n? - spamgolden 2018-11-20 20:41
Ty chyba nie najlepiej to rozumiesz. Przecież jak zwiększysz indeksowanie, to wyjdziesz jeszcze bardziej poza zakres. Zamiast new int *[W]; zrób new int *[n]; - GutekSan 2018-11-20 20:44

Pozostało 580 znaków

2018-11-20 20:22

Rejestracja: 1 rok temu

Ostatnio: 9 miesięcy temu

2

Zrób najperw refactor, ładnne zmienne i funkcje.

Pozostało 580 znaków

Odpowiedz

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