Cod sursa(job #710529)
Utilizator | Tudor Popa crazzytud | Data | 9 martie 2012 21:07:17 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include<stdio.h>
int g[5005],p[5005],optim[10001];
int main()
{
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
int n,G,i,j,sol=0;
scanf("%d%d",&n,&G);
for(i=1;i<=n;i++)
scanf("%d%d",&g[i],&p[i]);
for(i=1;i<=n;i++)
{
for(j=G-g[i];j>=0;j--)
if(optim[j+g[i]]<optim[j]+p[i])
{
optim[j+g[i]]=optim[j]+p[i];
if(sol<optim[j+g[i]])
sol=optim[j+g[i]];
}
}
printf("%d",sol);
}