Cod sursa(job #1768060)
Utilizator | Data | 30 septembrie 2016 09:20:52 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | c | Status | done |
Runda | Arhiva educationala | Marime | 0.48 kb |
#include <stdio.h>
long v[10001];
int g[5001], p[5001];
int main () {
FILE *fin, *fout;
fin=fopen("rucsac.in", "r");
fout=fopen("rucsac.out", "w");
int n, G, i, j;
fscanf(fin,"%d%d", &n, &G);
for(i=1;i<=n;i++)
fscanf(fin,"%d%d", &g[i], &p[i]);
for(i=1;i<=n;i++)
for(j=G;j>=g[i];j--) {
if(v[j]>v[j-g[i]]+p[i] )
v[j]=v[j];
else
v[j]=v[j-g[i]]+p[i];
}
fprintf(fout,"%d", v[G]);
fclose(fin);
fclose(fout);
return 0;
}