Cod sursa(job #617235)
Utilizator | Ionut Bogdanescu swift90 | Data | 14 octombrie 2011 12:39:16 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.42 kb |
#include<stdio.h>
int N,G,sol[10100];
int main(){
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
int i,j,w,p;
scanf("%d%d",&N,&G);
sol[0]=1;
for(i=0;i<N;++i){
scanf("%d%d",&w,&p);
for(j=G-w;j>=0;--j){
if(sol[j]+p>sol[j+w])
sol[j+w]=sol[j]+p;
}
}
p=0;
for(i=0;i<=G;++i){
if(sol[i]>p)
p=sol[i];
}
printf("%d\n",p-1);
fclose(stdin);
fclose(stdout);
return 0;
}