Cod sursa(job #767327)
Utilizator | Data | 13 iulie 2012 12:10:01 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
#include<iostream>
#include<fstream>
#include<bitset>
using namespace std;
int c[5001],gr[5001],cmax[2][10001];
int main ()
{
int n,i,gmax,s,l;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
f>>n>>gmax;
for(i=1;i<=n;i++)
f>>gr[i]>>c[i];
f.close();
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];
}
g<<cmax[l][gmax];
return 0;
}