Cod sursa(job #813403)
Utilizator | Data | 15 noiembrie 2012 13:41:21 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define Nmax 10001
int n, gr;
int g[Nmax];
int c[Nmax];
int v[Nmax];
int main()
{
fin >> n >> gr;
for( int i = 1; i <= n; ++i )
fin >> g[i] >> c[i];
for( int i = 1; i <= n; ++i )
for( int j = gr - g[i]; j >= 0; j-- )
v[j + g[i]] = max( v[j + g[i]], v[j] + c[i] );
fout << v[gr];
fin.close();
fout.close();
return 0;
}