Cod sursa(job #1772244)
Utilizator | Ioana Draganescu IoanaDraganescu | Data | 6 octombrie 2016 16:41:17 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.66 kb |
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N, G;
int d[2][10005];
int g[5005], v[5005];
int main()
{
fin >> N >> G;
for (int i = 1; i <= N; i++)
fin >> g[i] >> v[i];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= G; j++)
{
if (j >= g[i])
d[1][j] = max(d[0][j], v[i] + d[0][j - g[i]]);
else
d[1][j] = d[0][j];
}
for (int j = 1; j <= G; j++)
{
d[0][j] = d[1][j];
d[1][j] = 0;
}
}
fout << d[0][G] << '\n';
return 0;
}