Cod sursa(job #1119420)
Utilizator | Data | 24 februarie 2014 17:38:39 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <stdio.h>
using namespace std;
int n ,G ,profit[10001] ,val[5001] ,g[5001] ,i , j;
FILE *fin ,*fout;
int main()
{
fin=fopen("rucsac.in" ,"r");
fout=fopen("rucsac.out" ,"w");
fscanf(fin , "%d%d" ,&n ,&G);
for(i=1;i<=n;i++)
{
fscanf(fin , "%d%d" ,&g[i] ,&val[i]);
}
for(j=1;j<=G;j++) profit[j]=-1;
profit[0]=0;
for(i=1;i<=n;i++)
for(j=G-g[i];j>=0;j--)
{
if(profit[j]!=-1 && profit[j]+val[i]>profit[j+g[i]]) profit[j+g[i]]=profit[j]+val[i];
}
fprintf(fout ,"%d" ,profit[G]);
return 0;
}