Witam,
Jako zadanie mam napisać program rozwiązujący problem plecakowy przy użyciu algorytmu z nawrotami. Udało mi się napisać dotychczas coś takiego:
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
void otworz(ifstream &file)
{
while(true) //Pêtla wykonuje siê do momentu otwarcia pliku
{
string nazwa_pliku;
cout << "Podaj nazwe pliku : ";
getline(cin,nazwa_pliku); //pobranie nazwy pliku
//sprawdzamy czy u¿ytkownik poda³ nazwe z rozszerzeniem, je¿eli nie to dopisujemy do nazwy *.txt
file.open(nazwa_pliku.c_str());
if(file.is_open()) return;
file.open((nazwa_pliku+".txt").c_str());
if(file.is_open()) return;
//Je¿eli u¿ytkownik poda³ nieprawid³ow¹ nazwê pliku zwracamy komunikat
cout<<"Podana nazwa pliku jest nieprawid³owa! Plik nie istnieje"<<endl;
};
}
void plikdozapisu(ofstream &file)
{
while(true) //Pêtla wykonuje siê do momentu otwarcia pliku
{
string nazwa_pliku;
cout << "Podaj nazwe pliku : ";
getline(cin,nazwa_pliku); //pobranie nazwy pliku
//sprawdzamy czy u¿ytkownik poda³ nazwe z rozszerzeniem, je¿eli nie to dopisujemy do nazwy *.txt
file.open(nazwa_pliku.c_str());
if(file.is_open()) return;
file.open((nazwa_pliku+".txt").c_str());
if(file.is_open()) return;
//Je¿eli u¿ytkownik poda³ nazwe nieistniajacego pliku to zostanie on utworzony.
};
}
void Uzupelnij(ifstream &file, int n, int W, int &maxprofit, int *&Wartosc, int *&Waga, double *&Stosunek, int *&LewaStrona)
{
Wartosc[0]=Wartosc[n+2]=0;
Waga[n+2]=W;
Waga[0]=0;
Stosunek[0]=Stosunek[n+2]=0;
LewaStrona[0] = 0;
maxprofit=0;
}
void wczytaj(ifstream &file, int &n, int &W, int *&Wartosc, int *&Waga, double *&Stosunek, int *&LewaStrona)
{
file >> W;
file >> n;
Wartosc = new int [n+2];
Waga = new int [n+2];
Stosunek = new double [n+2];
LewaStrona = new int [n+1];
double stosunek;
int i;
stosunek = 0;
for (i=1; i < n+1; i++)
{
file >> Wartosc[i];
file >> Waga[i];
stosunek = Wartosc[i] / Waga[i];
Stosunek[i] = stosunek;
LewaStrona[i]=0;
};
}
void SortowanieDanych(int n, int *&Wartosc, int *&Waga, double *&Stosunek)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(Stosunek[j]<Stosunek[j+1])
{
swap(Stosunek[j],Stosunek[j+1]);
swap(Waga[j],Waga[j+1]);
swap(Wartosc[j],Wartosc[j+1]);
}
};
};
}
void wypisz(int n, int *Wartosc, int *Waga, double *Stosunek)
{
int i;
for (i=1; i <= n; i++)
{
cout << Wartosc[i] << " ";
cout << Waga[i] << " ";
cout << Stosunek[i] << " ";
cout << endl;
};
}
void plecak(int indeks1, int indeks2, int &k, int profit, int weight, int totalweight, ofstream &file, int *Wartosc, int *Waga, int W, int maxprofit, double *Stosunek, int n, int *LewaStrona)
{
file << "wezel (" << indeks1 << "," << indeks2 << ")\n";
//bierzemy przedmiot jeśli b jest nieparzyste
if (indeks2%2==1) {
file << "Bierzemy element nr " << indeks1 << "\n";
profit+=Wartosc[indeks1];
weight+=Waga[indeks1];
}
else
file << "Nie bierzemy elementu nr " << indeks1 << "\n";
file << "zysk = " << profit << "\nwaga = " << weight;
//jeśli przekroczona została waga to węzęł jest nieobiecujący
if (weight>=W)
file << "\nwaga >= pojemnosc - wezel nieobiecujacy\n";
else {
//aktualizacja maksymalnego zysku
if (profit>maxprofit) {
maxprofit = profit;
file << "\nNowy maks_zysk: " << maxprofit;
}
//obliczanie k
k = indeks1;
int zmienna = weight;
while (zmienna <= W)
zmienna+=Waga[++k];
file << "\nk = " << k;
//obliczanie sumy wag i granicy
int totalweight=weight;
int granica = profit;
for (int i = indeks1+1; i < k; ++i) {
totalweight+=Waga[i];
granica+=Wartosc[i];
}
granica+=(W-totalweight)*Stosunek[k];
file << "\nsuma_wag = " << totalweight;
file << "\ngranica: " << granica;
if (granica<=maxprofit) {
file << "\ngranica <= maks_zysk - wezel nieobiecujacy\n";
}
else {
//węzęł jest obiecujący - przechodzimy do lewego potomka
file << "\n---------------\n";
if (indeks1<n)
if (LewaStrona[indeks1+1]%2==0)
++LewaStrona[indeks1+1];
plecak(indeks1+1,LewaStrona[indeks1+1],k,profit,weight,totalweight, file, Wartosc, Waga, W, maxprofit, Stosunek, n, LewaStrona);
}
}
//węzeł nieobiecujący lub doszliśmy do liścia
file << "DO GORY\n---------------\n";
// jeśli braliśmy przedmiot (b nieparzyste) to pomijamy ten element w kolejnym wywołaniu
if (indeks2%2==1 && indeks1>0)
plecak(indeks1,++LewaStrona[indeks1],k,profit-Wartosc[indeks1], weight-Waga[indeks1], totalweight, file, Wartosc, Waga, W, maxprofit, Stosunek, n, LewaStrona);
}
int main()
{
ifstream plik;
ofstream file;
int n,W,maxprofit,profit,index1,index2,weight,totalweight,k;
int *Wartosc;
int *Waga;
int *LewaStrona;
double *Stosunek;
otworz(plik); //otwieramy plik z danymi
wczytaj(plik,n,W,Wartosc,Waga,Stosunek,LewaStrona);
Uzupelnij(plik,n,W,maxprofit,Wartosc,Waga, Stosunek,LewaStrona);
SortowanieDanych(n,Wartosc,Waga,Stosunek);
wypisz(n,Wartosc,Waga,Stosunek);
plikdozapisu(file);
plecak(0,0,k,0,0,totalweight, file, Wartosc, Waga, W, maxprofit, Stosunek, n, LewaStrona);
getchar();
getchar();
return 0;
}
Działa poprawnie do momentu wyświetlenia posortowanych tablic z danymi. Sam algorytm wysypuje do pliku nie prawidłowe rezultaty. Nie potrafię się doszukać, gdzie w algorytmie jest błąd. Z góry dziękuje za pomoc, zaznaczam od razu, że jestem początkujący i liczę na wyrozumiałość.
Z góry dzięki za pomoc,