Cod sursa(job #1673175)
| Utilizator | Data | 3 aprilie 2016 15:17:51 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 35 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.43 kb |
#include <fstream>
#define MAX 5000
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int rucsac[MAX+5][MAX*2+5] , N , G , w , p;
int main()
{ fin >> N >> G;
for(int i=1;i<=N;i++)
{ fin >> w >> p;
for(int j=1;j<w;j++)
rucsac[i][j]=rucsac[i-1][j];
for(int j=w;j<=G;j++)
rucsac[i][j]=max(rucsac[i-1][j-w]+p,rucsac[i-1][j]);
}
fout << rucsac[N][G] << '\n';
return 0;
}
