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