Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Algorytm Plecakowy z nawrotami

Ostatnio zmodyfikowano 2013-05-05 13:07
Autor Wiadomość
booyaka
Temat założony przez niniejszego użytkownika
Algorytm Plecakowy z nawrotami
» 2013-05-05 09:53:13
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:

C/C++
#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,
P-82069
DejaVu
» 2013-05-05 13:07:54
http://forum.4programmers.net/Newbie/216327-algorytm_plecakowy_z_nawrotami

No... najlepiej wkleić na X serwisów swój problem i czekać, aż problem się rozwiąże :)

/edit:
Podstawowy błąd to fakt, że w C++ tablice indeksowane są zawsze od 0, a nie od 1. Ty przepisywałeś kod zapewne napisany w pascalu, a tam tablice można indeksować jak się chce i większość osób numeruje je od 1 (bo tak książki uczą).
P-82092
« 1 »
  Strona 1 z 1