Cod sursa(job #1097005)
Utilizator | Tran Bach Lam TBLam99 | Data | 2 februarie 2014 20:31:15 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.16 kb |
#include<stdio.h>
int n,i,j,g,a,b,maxim,maximus;
int f[10001];
int main()
{
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
scanf("%d%d",&n,&g);
scanf("%d%d",&a,&b);
f[a]=b;
maxim=b;
for(i=2;i<=n;++i)
{
scanf("%d%d",&a,&b);
for(j=maxim;j>=1;--j)
if(f[j]!=0)
{
if((j+a)<=g)
{
f[j+a]=f[j]+b;
if(f[j+a]>=maximus)
maximus=f[j+a];
if((j+a)>maxim)
maxim=j+a;
}
}
if(a<=g)
{
f[a]=b;
if(f[a]>=maximus)
maximus=f[a];
if(a>maxim)
maxim=a;
}
}
printf("%d\n",maximus);
return 0;
}