Cod sursa(job #2302399)
Utilizator | Data | 14 decembrie 2018 16:25:44 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 50 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <iostream>
#include <fstream>
using namespace std;
int d[5005][10005], w[5005], p[5005];
int main()
{
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int N, G;
in >> N >> G;
for(int i = 1; i <= N; i++)
in >> w[i] >> p[i];
for(int i = 1; i <= N; i++)
{
for(int j = 0; j <= G; j++)
if (j >= w[i])
d[i][j] = max(d[i - 1][j], d[i - 1][j - w[i]] + p[i]);
else
d[i][j] = d[i - 1][j];
}
out << d[N][G];
return 0;
}