Cod sursa(job #610826)
Utilizator | Panaete Adrian proflaurian | Data | 29 august 2011 14:11:15 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.44 kb |
#include<cstdio>
int n,i,w,W,V,v[10010];
int main()
{
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
scanf("%d%d",&n,&w);
for(i=1;i<=w;i++)v[i]=1<<31;
for(;n;n--)
{
scanf("%d%d",&W,&V);
for(i=w-W;i>=0;i--)
if(v[i]>=0)
v[i+W]=v[i+W]>v[i]+V?v[i+W]:v[i]+V;
}
for(i=1,V=0;i<=w;i++)V=V>v[i]?V:v[i];
printf("%d\n",V);
return 0;
}