Dynamiczne programowanie problem plecakowy

Dynamiczne programowanie problem plecakowy
SP
  • Rejestracja:ponad 6 lat
  • Ostatnio:ponad 3 lata
  • Postów:57
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:

Kopiuj
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:

Kopiuj
#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
flowCRANE
Taguj wątki nazwami języków/technologii, nie bzdurami w stylu programowanie.
MarekR22
zmień też tytuł, np na: "Dynamiczne programowanie problem plecakowy", bo ten obecny jest nic nie znaczącą watą słowną.
GS
  • Rejestracja:prawie 9 lat
  • Ostatnio:około 11 godzin
  • Postów:1265
1
spamgolden napisał(a):
Kopiuj
 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: flowCRANE
SP
to jest dynamiczne tworzenie tablicy dwuwymiarowej
GS
Wiem. Ale wydaje mi się, że źle indeksowane.
GS
Jeśli n>W, wyjdziesz poza zakres.
GS
zależy ile wynosi W.
SP
masz rację,ale nie do końca. Zwiększyłem W do 11 i działało. Później zmniejszyłem do 7 i przestało działać. następnie zwiększyłem do 8 i znów działało. Ktoś ma pomysł jak to naprawić?
GS
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.
SP
a wiesz może jak naprawić to? bo w tym programie często będzie zdarzała sie sytuacja że n<W
GS
SP
zwiększyć indeksowanie? i indeksować do W+n?
GS
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];
B1
  • Rejestracja:ponad 6 lat
  • Ostatnio:prawie 6 lat
  • Postów:4
2

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

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.