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?
C++
programowanie.