Problema rucsacului knapsack.cpp

knapsack.cpp

/*

Divide et impera versus Dynamic Programming

                           f(5) 

                   f(4)               f(3)    
 
                f(3) f(2)           f(2)   f(1) 

             f(2) f(1) f(1) f(0)   f(1) f(0) 

           f(1) f(0)  

           overlapping suprapunere 

           1 2 3
                      5 6 7

                      1 2 3 4 5 6 7
                      divideetimpera(li,m)
                      divideetimpera(m+1, ls)
                      interclasare()


Problema Rucsacului (cazul discret) 0/1
---------------------------------------

O persoana are la dispozitie un rucsac cu  o capacitate de G unitati de greutate si intentioneaza
sa efectueze un transport in urma caruia sa obtina un castig. 
Persoana are la dispozitie N obiecte.

Pentru fiecare obiect cunoaste Greutatea sa Gr(i) (numar natural) si castigul obtinut in urma trasportului
sau C(i) 


Ce obiecte trebuie sa aleagas persoana pentru a-si maximiza castigul care care este acesta?

input:

5 obiecte
10 kg- capacitatea rucsacului (vapor)
5 10
3 2
4 3
3 8
10 12
5 7

Notam obiectele cu 1, 2,3,....,n 

Exista posibilitatea  ca problema sa admita  mai multe solutii optime 

Fie S = {i1,i2,..,ik} o solutie optima a problemei  unde i1 < u2 < ...<ik obiecte din cele n


Daca se inlatura obiecte ik atunci greutatea G - Gr(ik) este incarcata optim cu obiectele

i1, i2,...,ik-1 


Daca prin absurd ar exista o alta incarcare a rucsacului pentru greutatea G - Gr(ik) , care aduce un castig mai mare

atunci, la acea incarcatura s-ar adauga si  obiect ik. am obtine o solutie mai buna decat cea initiala, ceea ce contrazice optimalitatea solutiei


Aceasta conduce la urmatoarea idee de rezolvare a problemei:

- capacitatile 1,2,...,G se incarca optim, la inceput cu obiectul 1, 
apoi se imbunatateste solutia cu obiectul 2, ...., si la sfarsit se imbunatateste solutia cu obiectul n


- pentru a calcula castigul maxim vom utiliza 

matricea Castig i,c


Castig(1,0) = 0  i = 1...n

castig(0,j) = 0 j = 1...G

a)Daca rucsacul are capacitatea 0 evident nu poate fi trasportat nicun obiect

in concluzie castigul este 0
b) daca nu trasportam niciun obiect indiferent de capacitate , castigul obtinut este 0


c) cazul corespunde deciziei de a alege sau nu pentru greutate j produsul i

daca pentru greutatea j se alege produsul i , atunci castigul care se obtine este suma dintre castigul maxim obtinut pentru 

capacitatea G - Gr(i) la care se adauga castigul obtinut din trasportul obiectului i. 
Daca nu se alege spre transport obiectul i, atunci ne multumim  cu castigul maxim obtinut pentru greutatea j
in cazul in care se trasnporta doar obiecte alese dintre primele i-1

alegem sau nu obiectul i pentru transport in functie de castigul care se obtine , care trebuie sa fie MAXIM



                  Castig(i-1, j - Gr(i) + Cost(i)) , daca Castig(i-1, j-Gr(i) + cost(i)) > Castig(i-1, j)


Castigul(i,j) =   Castig(i-1,j)                          altfel


DP = Dynamic Programming

for(int i = 1; i<=n; ++) {
	      
        for(int j = 0; j <= G; ++j) {
	

        } 
}
    0 1 2 3 4 5 6 7 8 9 10   (Greutati)
i = 0 0 0 0 0 0 0 0 0 0 0
i = 1 0 0 2 2 2 2 2 2 2 2
i = 2 0 0 0    
i = 3
i = 4
i = 5                                  

DP[5][10]

DP[n][G]

5 obiecte
10 kg- capacitatea rucsacului (vapor)

    5 10
obiect, greutate, profit
i=1: 3 2

i=2: 4 3

i=3: 3 8

i=4: 10 12

i=5: 5 7


*/

#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>

using namespace std;


int main(int argc, char const *argv[])
{

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, G;

fin>>n>>G;//citim numarul de obiecte si capacitatea rucsacului

//cout<<n<<" "<<G;

vector<int> g(n+1), 
            p(n+1);

for(int i = 1; i <= n; ++i) {

    fin>>g[i]>>p[i];	//citim greutate,profit pentru fiecare obiect    
}

vector<vector<int>> DP(n+1, vector<int>(G+1, 0)); //matricea costurilor

for(int i = 1; i <= n; ++i) {

	    for(int j = 0; j <= G; j++) {

	    	 if(g[i] > j) {//nu incape in capacitate

	    	 	  DP[i][j] = DP[ i - 1 ][ j ];

	    	 } else {
	    	 	//daca incape in rucsac
     	    	 DP[i][j] = max( DP[i - 1][ j ], DP[i-1][ j - g[ i ] ] + p[i]);	

	    	 }
	    }
}

//DP[i][j] = profitul pe care il obtin cu primele obiecte i incarcand cu greutate j

//profitul optim va fi in matrice la DP[n][g];

//afisare Table DP
fout<<"Tabel Castig (DP): \n\n";

//header pentru coloane

fout<<"    ";
for(int j = 0; j <= G; ++j) {

	fout<<setw(3)<<j;
}

fout<<"\n";

for(int i = 0; i <= n; ++i) {

	  fout<<"i="<<i<<" ";

	  for(int j = 0; j <= G; ++j) {

	  	  fout<<setw(3)<<DP[i][j];
	  }
	  fout<<"\n";
}

//profit maxim

fout<<"Profit maxim: "<<DP[n][G]<<"\n";

//reconstruire solutie
int j = G;

vector<int> obiecte;

for(int i = n; i >= 1; i--) {

	  if(DP[i][j] != DP[i-1][j]) {

            obiecte.push_back(i);

            j -= g[i]; 
	  }
}

fout<<"Obiecte alese: ";

for(int i = obiecte.size()-1; i >=0 ; i--) {

	fout<<obiecte[i]<<" ";
}

fout<<"\n";


	
	return 0;
}