Cod sursa(job #767330)
#include<iostream>
#include<fstream>
#include<stdio.h>
using namespace std;
int c[5001],gr[5001],cmax[2][10001];
int main ()
{
int n,i,gmax,s,l;
FILE *f=fopen("rucsac.in","r");
FILE *g=fopen("rucsac.out","w");
fscanf(f,"%d %d",&n,&gmax);
for(i=1;i<=n;i++)
fscanf(f,"%d %d",&gr[i],&c[i]);
fclose(f);
l=0;
for(i=1;i<=n;i++,l=1-l)
for(s=0;s<=gmax;s++) {
cmax[1-l][s]=cmax[l][s];
if((gr[i]<=s)&&(cmax[1-l][s]<(cmax[l][s-gr[i]]+c[i])))
cmax[1-l][s]=cmax[l][s-gr[i]]+c[i];
}
fprintf(g,"%d",cmax[l][gmax]);
fclose(g);
return 0;
}