Cod sursa(job #609570)
Utilizator | Paul Buda paul_gabryel | Data | 22 august 2011 12:32:42 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 65 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.41 kb |
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
int g[5001],p[5001],d[2][10001],n,i,j,G,k;
int main ()
{
ifstream f ("rucsac.in");
freopen ("rucsac.out","w",stdout);
f>>n>>G;
for(i=1;i<=n;++i)
f>>g[i]>>p[i];
for(i=1;i<=n;++i,j=1-j)
for(k=0;k<=G;++k){
d[1-j][k]=d[j][k];
if(g[i]<=k)
d[1-j][k]=max(d[1-j][k],d[j][k-g[i]]+p[i]);
}
printf("%d",d[j][G]);
return 0;}