Cod sursa(job #2854410)
| Utilizator | Data | 21 februarie 2022 13:05:57 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.63 kb |
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int main()
{
int n, g, profit = 0;
in >> n >> g;
int dp[n + 1][g + 1], w[n], p[n];
for (int i = 1; i <= n; i++)
in >> w[i] >> p[i];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= g; j++)
{
if (!i || !j)
dp[i][j] = 0;
else{ if (w[i] <= j)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
else
dp[i][j] = dp[i - 1][j];
}
}
out << dp[n][g];
return 0;
}