Cod sursa(job #1174319)
| Utilizator | Data | 22 aprilie 2014 15:48:50 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.62 kb |
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int w[5001] , c[5001] , d[10001];
int main()
{
int n , g , i , j , maxim;
in>>n>>g;
for(i = 1 ; i <= n ; i++)
in>>w[i]>>c[i];
for (j = 1; j <= g; j++)
d[j] = -1;
d[0] = 0;
for(i = 1 ; i <= n ; i++)
for(j = g; j >= w[i] ; j--)
{
if(d[j - w[i]] >= 0)
d[j] = max(d[j] , d[j - w[i]] + c[i]);
}
maxim = 0;
for(j = 1 ; j <= g ; j++)
maxim = max(maxim , d[j]);
out<<d[g]<<'\n';
return 0;
}
