Cod sursa(job #1323038)
| Utilizator | Data | 20 ianuarie 2015 16:52:25 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.61 kb |
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
const int N = 5001;
const int G = 10001;
int w[N], p[N], d[G];
int main()
{
int n, g, nrmax = 0;
register int i;
register int j;
in >> n >> g;
for ( i = 1; i <= n; i++ )
in >> w[i] >> p[i];
for ( i = 1; i <= n; i++ )
for ( j = g - w[i]; j >= 0; j-- )
{
d[ j + w[i] ] = max( d[ j + w[i] ], d[j] + p[i] );
}
for ( i = 0; i <= g; i++ )
if ( nrmax < d[i] )
nrmax = d[i];
out << nrmax;
return 0;
}
