Cod sursa(job #3358712)
| Utilizator | Data | 19 iunie 2026 16:34:24 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.5 kb |
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main() {
int n, g;
fin >> n >> g;
vector<int> w(n+1), p(n+1);
for (int i = 1; i <= n; i++)
fin >> w[i] >> p[i];
vector<int> dp(g+1, 0);
for (int i = 1; i <= n; i++)
for (int cw = g; cw >= w[i]; cw--)
if (dp[cw - w[i]] + p[i] > dp[cw])
dp[cw] = dp[cw - w[i]] + p[i];
fout << dp[g];
return 0;
}