Cod sursa(job #894441)
#include <iostream>
#include <fstream>
using namespace std;
int n,C; // n-nr de obiecte; C-capacitatea rucsacului
int greutate[5001],profit[5001];
/* greutate[i]= greutatea obiectului i
profit[i]= profitul adus de obiectul i
*/
int Solutie[5001][10001];//aici calculez solutia problemei
//Solutie[n][C] = solutia problemei
int maxim(int a,int b)
{
return a > b ? a : b;
}
int calculeazaSolutieMatrice()
{
for(int i=1;i<=n;i++)
for(int j=0;j<=C;j++)
if(j>=greutate[i])//daca am loc in rucsac pentru obiectul i
{
Solutie[i][j] = maxim ( Solutie[i-1][j],Solutie[i-1][j-greutate[i]]+profit[i]);
/* Solutie[i-1][j] = solutia problemei fara a alege obiectul i
Solutie[i-1][j-greutate[i]]+profit[i] = solutia pb din profitul adus de obiectul i(profit[i])
si cea mai buna solutie fara greutatea obiectului i( adica Solutie[i-1][j-greutate[i]] )
*/
}
else //nu am loc in rucsac
Solutie[i][j]=Solutie[i-1][j];// adica cea mai buna solutie fara obiectul i
return Solutie[n][C];
}
int main()
{
ifstream in("rucsac.in");
in>>n>>C;
for(int i=1;i<=n;++i)
in>>greutate[i]>>profit[i];
in.close();
ofstream out("rucsac.out");
out<<calculeazaSolutieMatrice();
out.close();
return 0;
}