Cod sursa(job #1431310)
Utilizator | Cristian Coman cristi26 | Data | 9 mai 2015 10:26:32 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <iostream>
#include<cstdio>
using namespace std;
int N,G,v[10001],g,p,i,j;
int main()
{
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","W",stdout);
scanf("%d%d",&N,&G);
for(i=1;i<=G;i++)
v[i]=-1;
v[0]=0;
for(i=1;i<=N;i++)
{
scanf("%d%d",&g,&p);
for(j=G-g;j>=0;j--)
{
if(v[j]!=-1)
{
if(v[j+g]<v[j]+p)
v[j+g]=v[j]+p;
}
}
}
int Max=0;
for(i=1;i<=G;i++)
if(Max<v[i])
Max=v[i];
printf("%d",Max);
return 0;
}