Cod sursa(job #641973)
Utilizator | Data | 30 noiembrie 2011 10:03:35 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.41 kb |
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int profit[10003],W[5005],P[5005];
int N,G;
int main() {
fin >> N >> G;
for(int i=1;i<=N;++i) fin >> W[i] >> P[i];
for(int i=1;i<=G;++i)
profit[i]=-1;
for(int i=1;i<=N;++i)
for(int j=G-W[i];j>=0;--j)
profit[j+W[i]]=max(profit[j+W[i]],profit[j]+P[i]);
fout << profit[G];
return 0;
}