Problema rucsacului

Enunț:

Problema rucsacului, varianta în care nu se permite fracționarea obiectelor. (Problema continuă a rucsacului). Avem la dispoziție n obiecte, fiecare cu o anumită masă (mi) și un anumit câștig (ci), care s-ar obține prin transportul obiectului i în întregime. Se pune problema ce obiecte să selectăm pentru a le transporta cu un rucsac care are o capacitate maximă M, astfel încât să obținem un câștig maxim.

Indicație de rezolvare:

Am văzut că, în acest caz, în care nu este permisă fracționarea obiectelor, metoda Greedy nu ne furnizează întotdeauna soluția optimă.

Presupunem că măcar un obiect are masa mai mică decât M. Vom folosi tabloul bidimensional D, cu n+1 linii și M+1 coloane, în care vom păstra soluțiile subproblemelor: D[i][j] este cel mai bun câștig obținut pentru primele i obiecte, având masa însumată j. Soluția se construiește astfel: dacă D[n][M] este câștigul maxim obținut prin selectarea unei submulțimi de obiecte din cele n disponibile, care nu depășesc masa totală care poate fi transportată în rucsac, M, atunci relația de recurență este:

D[n][M]=maxim(D[n-1][M],D[n-1][M-m_n]+c_n)

Astfel, câștigul maxim se obține fie fără a adăuga obiectul n, rămânând la câștigul obținut pentru n-1 obiecte, fie prin adăugarea obiectului n, caz în care se adaugă la câștigul obținut pentru n-1 obiecte și greutate M-m_n, cel rezultat prin transportul obiectului n. Ideea algoritmului este deci următoarea: la fiecare pas, la soluția curentă ori nu adăugăm deloc obiectul i, și rămânem la câștigul obținut pentru i-1 obiecte, ori adăugăm obiectul i, caz în care adăugăm obiectul i, caz în care adăugăm câștigul rezultat prin transportul lui la cel obținut pentru primele i-1 obiecte și greutate j-m_i. Obținem formula de recurență:

Implementare:

Cod Sursa C++

// RucsacDinamicCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#define dim 100
 
using namespace std;
 
int D[dim][dim], m[dim], c[dim], n, M, sol[dim], S[dim][dim];
 
int max(int a, int b)
{
	if (a > b)
		return a;
	else
		return b;
}
 
//varianta ascendenta
void rucsac1()
{
	int i, j;
	//tabloul D are n+1 linii si M+1 coloane
	for (i = 0; i < n; i++)
	{
		for (j = 0; j <= M;j++)
		if (j < m[i])
			D[i + 1][j] = D[i][j];
		else
			D[i + 1][j] = max(D[i][j], D[i][j - m[i]] + c[i]);
	}
	cout << "Castigul total: " << D[n][M] << endl;
}
 
//tehnica memoizarii
int rucsac2(int i, int j)
{
	//implementare recursiva
	//valorile intermediare necesare obtinerii solutiei se stocheaza
	if (i == 0 || j == 0)
	{
		S[i][j] = 0;
		return S[i][j];
	}
	else
	if (S[i][j] != -1)
		return S[i][j];
	else
	{
		if (j < m[i])
			S[i][j] = rucsac2(i - 1, j);
		else
			S[i][j] = max(rucsac2(i - 1, j), 
			rucsac2(i - 1, j - m[i]) + c[i]);
		return S[i][j];
	}
}
 
void constructSol()
{
	int i = n, j = M;
	while (D[i][j] > 0)
	{
		if (D[i][j] == D[i - 1][j])
			i = i - 1;
		else
		{
			sol[i - 1] = 1;
			j = j - m[i - 1];
			i = i - 1;
		}
	}
}
 
int main()
{
	cout << "n= ";
	cin >> n;
	cout << "M= ";
	cin >> M;
	for (int i = 0; i < n; i++)
	{
		cout << "m[" << i << "]=";
		cin >> m[i];
	}
	for (int i = 0; i < n; i++)
	{
		cout << "c[" << i << "]=";
		cin >> c[i];
	}
	cout << "1. Varianta ascendenta." << endl;
	rucsac1();
	cout << "Obiectele seletate: ";
	constructSol();
	for (int i = 0; i < n;i++)
	if (sol[i])
		cout << i + 1 << " ";
	cout << endl;
	cout << "2. Tehnica memoizarii." << endl;
	//initializarea matricei cu o valoarea virtuala
	for (int i = 0; i <= n;i++)
	for (int j = 0; j <= M; j++)
		S[i][j] = -1;
	int optim = rucsac2(n, M);
	cout << "Castigul total: " << optim << endl;
	cout << endl;
	system("pause");
}

Rezultat: