Problem Plecakowy

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.

Ż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?

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?