booyaka Temat założony przez niniejszego użytkownika |
[C++] Algorytm Plecakowy. » 2013-04-15 23:04:05 Witam, Mam za zadanie napisać program rozwiązujący ogólny problem plecakowy przy użyciu programowania dynamicznego. Zakładamy, że każdego z możliwych do wyboru przedmiotów mamy nieograniczoną ilość. Algorytm na którym się wzoruje: Tablica wartości P[i,j] najlepszych upakowań plecaka o pojemności j rzeczami rodzajów od 1 do i; dla i=1,2,….,n oraz j=1,2,… Mmax. Tablica Qi,j skojarzona z Pi,j rzeczy Pi pakowanych do plecaka w ostatnim ruchu. 1) {Ustalenie wartości początkowych tablic P i Q rozszerzonych dla ujednolicenia obliczeń o wiersze i kolumny zerowe.} Dla j=1,2,…, Mmax przypisz P[0,j]:=0, Q[0,j]:=0 Dla i=1,2,…,n przypisz P[i,0]:=0, Q[i,0]:=0. 2) Dla kolejnych rzeczy i=1,2,…,n wykonaj krok 3. 3) Dla kolejnych pojemności plecaka j=1,2,… Mmax wykonaj krok 4. 4) Jeśli (j ≥ m[i] ) {Czyli pojemność plecaka jest wystarczająca, by pomieścić rzecz i} oraz P[i-1][j] < P[i][j - m[i] + c[i] to przypisz P[i-1][j] = P[i][j-m[i]] + c[i] oraz Q[i][j] = i, a w przeciwnym wypadku pozostaw wartości z poprzedniego wierszam czyli przepisz P[i][j] = P[i-1][j] oraz Q[i][j] = Q[i-1][j] Napisany przeze mnie kod wygląda następująco: #include <iostream>
#include <string>
int i, j, ilosc, pojemnosc;
using namespace std;
int main()
{
cout << "Podaj pojemnosc plecaka : ";
cin >> pojemnosc;
cout << "Podaj liczbe przedmiotow : ";
cin >> ilosc;
cout << endl;
string * p = new string[ ilosc ];
int * m = new int[ ilosc ];
int * c = new int[ ilosc ];
int ** Q = new int *[ ilosc + 1 ];
for( i = 0; i <= ilosc; ++i )
Q[ i ] = new int[ pojemnosc + 1 ];
int ** P = new int *[ ilosc + 1 ];
for( i = 0; i <= ilosc; ++i )
P[ i ] = new int[ pojemnosc + 1 ];
for( i = 0; i < ilosc; ++i )
{
cout << "Podaj nazwe przedmiotu : ";
cin >> p[ i ];
cout << "Podaj wage przedmiotu : ";
cin >> m[ i ];
cout << "Podaj wartosc przedmiotu : ";
cin >> c[ i ];
cout << endl;
};
for( i = 0; i <= ilosc; ++i ) {
P[ i ][ 0 ] = 0;
Q[ i ][ 0 ] = 0;
};
for( j = 0; j <= pojemnosc; ++j ) {
P[ 0 ][ j ] = 0;
Q[ 0 ][ j ] = 0;
};
for( i = 1; i <= ilosc; ++i ) {
for( j = 1; j <= pojemnosc; ++j ) {
if((( j >= m[ i - 1 ] ) &&( P[ i - 1 ][ j ] < P[ i ][ j - m[ i - 1 ] + c[ i - 1 ] ] ) ) )
{
P[ i ][ j ] = P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ];
Q[ i ][ j ] = i;
}
else {
P[ i ][ j ] = P[ i - 1 ][ j ];
Q[ i ][ j ] = Q[ i - 1 ][ j ];
};
};
};
cout << " Wypisanie tablicy P " << endl;
for( i = 1; i <= ilosc; ++i )
{
for( j = 1; j <= pojemnosc; ++j )
{
cout << P[ i ][ j ] << " ";
};
cout << endl;
};
getchar();
getchar();
return 0;
}
Program się kompiluje, ale zwraca nie do końca prawidłowe wartości. Testuje go na tym przykładzie: http://www-users.mat.uni.torun.pl/~henkej/knapsack.pdf (str. 5 w wykładzie) Nie mogę się doszukać gdzie tkwi problem. Z góry dziękuje za pomoc w poprawie błędów, |
|
DejaVu |
» 2013-04-16 10:45:21 Wypisuj P i Q po każdej modyfikacji - umożliwi Ci to stwierdzenie w którym miejscu pojawia się błąd w obliczeniach. |
|
booyaka Temat założony przez niniejszego użytkownika |
» 2013-04-17 20:08:39 Udało mi się poprawić kod, tak, że wszystko działa jak należy. Teraz muszę jeszcze podzielić na funkcje i z tym mam mały problem. Na początku wkleję kod: #include <iostream>
#include <string>
void PobierzDaneGlowne( int & ilosc, int & pojemnosc );
void UtworzTablice( int ilosc, int pojemnosc );
void PrzypiszWartoscidoTablic( int ilosc, int & m, int & p, int & c, int & P, int & Q );
void AlgorytmPlecakowy( int ilosc, int pojemnosc, int * p, int * m, int * c, int ** P, int ** Q );
void WypiszTabliceWynikow( int ilosc, int pojemnosc, int ** tab );
void WypiszWyniki( int ** P, int ** Q, int * p, int * m, int * c, int ilosc, int pojemnosc );
using namespace std;
int main()
{
int pojemnosc, ilosc;
int * m, * p, * c;
int ** P, ** Q;
PobierzDaneGlowne( ilosc, pojemnosc );
UtworzTablice( ilosc, pojemnosc );
PrzypiszWartoscidoTablic( ilosc, pojemnosc, m, p, c, P, Q );
AlgorytmPlecakowy( ilosc, pojemnosc, p, m, c, P, Q );
WypiszTabliceWynikow( ilosc, pojemnosc, P );
WypiszTabliceWynikow( ilosc, pojemnosc, Q );
WypiszWyniki( P, Q, p, m, c, ilosc, pojemnosc );
getchar();
getchar();
return 0;
}
void PobierzDaneGlowne( int & ilosc, int & pojemnosc )
{
cout << "Podaj pojemnosc plecaka : ";
cin >> pojemnosc;
cout << "Podaj liczbe przedmiotow : ";
cin >> ilosc;
cout << endl;
}
void UtworzTablice( int ilosc, int pojemnosc )
{
int i;
string * p = new string[ ilosc ];
int * m = new int[ ilosc ];
int * c = new int[ ilosc ];
int ** Q = new int *[ ilosc + 1 ];
for( i = 0; i <= ilosc; ++i )
Q[ i ] = new int[ pojemnosc + 1 ];
int ** P = new int *[ ilosc + 1 ];
for( i = 0; i <= ilosc; ++i )
P[ i ] = new int[ pojemnosc + 1 ];
}
void PrzypiszWartoscidoTablic( int ilosc, int pojemnosc, int & m, int & p, int & c, int & P, int & Q )
{
int i, j;
for( int i = 0; i < ilosc; ++i )
{
cout << "Podaj nazwe przedmiotu : ";
cin >> p[ i ];
cout << "Podaj wage przedmiotu : ";
cin >> m[ i ];
cout << "Podaj wartosc przedmiotu : ";
cin >> c[ i ];
cout << endl;
};
for( i = 0; i <= ilosc; ++i ) {
P[ i ][ 0 ] = 0;
Q[ i ][ 0 ] = 0;
};
for( j = 0; j <= pojemnosc; ++j ) {
P[ 0 ][ j ] = 0;
Q[ 0 ][ j ] = 0;
};
}
void AlgorytmPlecakowy( int ilosc, int pojemnosc, int * p, int * m, int * c, int ** P, int ** Q )
{
int i, j;
for( i = 1; i <= ilosc; ++i ) {
for( j = 1; j <= pojemnosc; ++j ) {
if(( j >= m[ i - 1 ] ) &&( P[ i - 1 ][ j ] <( P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ] ) ) ) {
P[ i ][ j ] = P[ i ][ j - m[ i - 1 ] ] + c[ i - 1 ];
Q[ i ][ j ] = i;
}
else {
P[ i ][ j ] = P[ i - 1 ][ j ];
Q[ i ][ j ] = Q[ i - 1 ][ j ];
}
}
};
}
void WypiszTabliceWynikow( int ilosc, int pojemnosc, int ** tab )
{
int i, j;
cout << " Tablica : " << endl;
for( i = 1; i <= ilosc; ++i )
{
for( j = 1; j <= pojemnosc; ++j )
{
cout << tab[ i ][ j ] << " ";
};
cout << endl;
};
}
void WypiszWyniki( int ilosc, int pojemnosc, int ** P, int ** Q, int * p, int * m, int * c )
{
cout << endl;
cout << "MAX : " << P[ ilosc ][ pojemnosc ] << endl;
while( pojemnosc > 0 )
{
cout << p[ Q[ ilosc ][ pojemnosc ] - 1 ] << "cena" << c[ Q[ ilosc ][ pojemnosc ] - 1 ] << endl;
pojemnosc -= m[ Q[ ilosc ][ pojemnosc ] - 1 ];
};
}
W jaki sposób mogę przekazywać tablice dynamiczne tj. *m, *p, *c, **P, **Q pomiędzy kolejnymi funkcjami? Zawsze się w tym gubię i nie mogę sobie z tym poradzić. Z góry napiszę, że mam świadomość, że to co dałem powyżej pewnie zawiera sporo błędów, ale proszę o wyrozumiałość. |
|
pekfos |
» 2013-04-17 20:10:54 Przekazuj te wskaźniki przez wartość lub referencje (gdy modyfikujesz wskaźnik). |
|
booyaka Temat założony przez niniejszego użytkownika |
» 2013-04-17 20:21:18 Nie potrafię zrozumieć jak to ma wyglądać, mógłbyś to po prostu rozpisać na przykładzie jednej z moich funkcji? Wtedy będę już wiedział na przyszłość jak to robić. |
|
pekfos |
» 2013-04-17 20:26:03 void f1( int * wartosc );
void f2( int *& referencja );
void f3( int ** wskaznik );
int * t;
f1( t );
f2( t );
f3( & t ); |
|
booyaka Temat założony przez niniejszego użytkownika |
» 2013-04-17 21:20:03 Dzięki wielkie pekfos, udało mi się to podzielić tak jak planowałem. |
|
| « 1 » |