Cod sursa(job #682934)
Utilizator | Alghisi Alessandro Paolo alexalghisi | Data | 19 februarie 2012 19:00:34 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[105][105];
int main()
{
int n,G,greutate,profit;
freopen("rucsac.in","r", stdin);
scanf("%d %d",&n,&G);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&greutate,&profit);
for(int g=0;g<=G;g++)
{
dp[i][g]=dp[i-1][g];
if(greutate<=g)
dp[i][g]=max(dp[i][g],dp[i][g-greutate]+profit);
for(int j=1;j<=n;j++)
{
cout<<endl;
for(int k=1;k<=G;k++)
cout<<dp[j][k]<<" ";
}
cout<<endl;
}
}
return 0;
}