Cod sursa(job #2493535)
| Utilizator | Data | 16 noiembrie 2019 13:38:59 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.52 kb |
#include <bits/stdc++.h>
#pragma warning(disable : 4996)
std::ifstream fin("rucsac.in");
std::ofstream fout("rucsac.out");
const int NMax = 5000;
const int GMax = 10000;
int n, g;
int w[NMax + 5];
int p[NMax + 5];
int mat[GMax + 5];
void dp(int n)
{
for (int i = g; i >= 1; i--)
if(i - w[n] >= 0)
mat[i] = std::max(mat[i], mat[i - w[n]] + p[n]);
}
int main()
{
fin >> n >> g;
for (int i = 1; i <= n; i++)
fin >> w[i] >> p[i];
for(int i = 1; i <= n; i++)
dp(i);
fout << mat[g];
}