Problem Plecakowy

0

Witam,

Mam za zadanie wykonać program rozwiązujący problem plecakowy za pomocą metody dynamicznej. Korzystam z algorytmu (pseudokodu) z wikipedii tj.


for i:=0 to n do
    A[i,0]:= 0
  for j:=0 to W do
    A[0,j]:= 0

  for i:=1 to n do           //rozważanie kolejno i pierwszych przedmiotów
    for j:=0 to W do
      if ( w[i] > j ) then   //sprawdzenie czy i-ty element mieści się w plecaku o rozmiarze j
        A[i,j] = A[i-1,j]
      else
        A[i,j] =  max(A[i-1,j], A[i-1,j-w[i]] + c[i])

Mój program natomiast wygląda następująco:


#include <iostream>
#include <string>

int i,j,ilosc,pojemnosc,maxi;

using namespace std;

int main()
{   

    cout << "Podaj pojemnosc plecaka : ";
    cin >> pojemnosc;
    cout << "Podaj liczbe przedmiotow : ";
    cin >> ilosc;
    cout << endl;

    string *Nazwy_Przedmiotow = new string [ilosc];
    int *Wagi_Przedmiotow = new int [ilosc];
    int *Wartosci_Przedmiotow = new int [ilosc];
    int **Wyniki = new int *[ilosc+1];

    for (i = 0; i < ilosc+1; ++i )
    Wyniki[i] = new int [pojemnosc+1];

    for (i=0; i < ilosc; i++)
    {
        cout << "Podaj nazwe przedmiotu : ";
        cin >> Nazwy_Przedmiotow[i];
        cout << "Podaj wage przedmiotu : ";
        cin >> Wagi_Przedmiotow[i];
        cout << "Podaj wartosc przedmiotu : ";
        cin >> Wartosci_Przedmiotow[i];
    };

    for (i=0; i < ilosc; i++)   Wyniki[i][0] = 0;
    for (j=0; j < pojemnosc; j++) Wyniki[0][j] = 0;

    for (i=1; i < ilosc; i++)
    {
        for (j=0; j < pojemnosc; j++)
        {
            if ( Wyniki[i-1][j] > (Wyniki[i-1][j-Wagi_Przedmiotow[i]] + Wartosci_Przedmiotow[i])) maxi = Wyniki[i-1][j];
            else maxi = (Wyniki[i-1][j-Wagi_Przedmiotow[i]] + Wartosci_Przedmiotow[i]);

            if ( Wagi_Przedmiotow[i] > j ) Wyniki[i][j] = Wyniki[i-1][j];
            else Wyniki[i][j] = maxi;
        };
    };

    cout << Wyniki[ilosc][pojemnosc] << endl;

  getchar();
  getchar();
  return 0;
}

Problem polega na tym, że wypisuje na końcu bzdurne wyniki. Podejrzewam, że błąd tkwi w którymś miejscu, gdzie przypisuje dane tablic, ale nie mogę się jego doszukać.

Z góry dziękuje za pomoc w poprawieniu kodu.

0

Żartujesz sobie, prawda?

if ( Wyniki[i-1][j] > (Wyniki[i-1][j-Wagi_Przedmiotow[i]] + Wartosci_Przedmiotow[i])) 
  maxi = Wyniki[i-1][j];
else 
  maxi = (Wyniki[i-1][j-Wagi_Przedmiotow[i]] + Wartosci_Przedmiotow[i]);
if ( Wagi_Przedmiotow[i] > j ) 
  Wyniki[i][j] = Wyniki[i-1][j];
else 
  Wyniki[i][j] = maxi;

vs.

if ( w[i] > j ) then
  A[i,j] = A[i-1,j]
else
  A[i,j] =  max(A[i-1,j], A[i-1,j-w[i]] + c[i])

Widzisz jakąś różnicę? o_O Szczególnie w kolejności warunków? U ciebie widzę odwołanie:

j-Wagi_Przedmiotow[i]

a nie widzę nigdzie testu czy j jest większe od Wagi_Przedmiotow[i]. A jak nie jest? To co? Ujemny indeks w tablicy? Srsly?

0

Shalom faktycznie źle to przepisałem, chyba kwestia zmęczenia i pisania późnym wieczorem. Mam nadzieje, że teraz poprawiłem to już dobrze i nie będziesz się więcej denerwował.


#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 *Nazwy_Przedmiotow = new string [ilosc];
    int *Wagi_Przedmiotow = new int [ilosc];
    int *Wartosci_Przedmiotow = new int [ilosc];
    int **Wyniki = new int *[ilosc+1];

    for (i = 0; i < ilosc+1; ++i )
    Wyniki[i] = new int [pojemnosc+1];

    for (i=0; i < ilosc; i++)
    {
        cout << "Podaj nazwe przedmiotu : ";
        cin >> Nazwy_Przedmiotow[i];
        cout << "Podaj wage przedmiotu : ";
        cin >> Wagi_Przedmiotow[i];
        cout << "Podaj wartosc przedmiotu : ";
        cin >> Wartosci_Przedmiotow[i];
        cout << endl;
    };

    for (i=0; i < ilosc; i++)   Wyniki[i][0] = 0;
    for (j=0; j < pojemnosc; j++) Wyniki[0][j] = 0;

    for (i=1; i < ilosc; i++)
    {
        for (j=0; j < pojemnosc; j++)
        {
            if (j-Wagi_Przedmiotow[i]>=0)

            if (Wagi_Przedmiotow[i] > j ) 
                Wyniki[i][j] = Wyniki[i-1][j];
            else
                Wyniki[i][j] = max(Wyniki[i-1][j], Wyniki[i-1][j-Wagi_Przedmiotow[i]] + Wartosci_Przedmiotow[i]);
        };
    };

    cout << Wyniki[ilosc-1][pojemnosc-1] << endl;

  getchar();
  getchar();
  return 0;
}

Kwestie ujemnego indeksu w tablicy o której faktycznie nie pomyślałem rozwiązałem taką linijką kodu, oceń czy jest wystarczająca:


if (j-Wagi_Przedmiotow[i]>=0)

Algorytm z tego co sprawdzałem to "prawie" działa. Problem polega na tym, że wszystkie wyniki z tablicy wypisuje o 1 mniejsze niż powinien. W czym problem?

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0