Cod sursa(job #3334152)
| Utilizator | Data | 16 ianuarie 2026 15:32:07 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.58 kb |
#include <iostream>
#include <fstream>
#include <vector>
std::ifstream in("rucsac.in");
std::ofstream out("rucsac.out");
int main() {
int n, g;
in >> n >> g;
std::vector<int> dp(g + 1);
std::vector<std::pair<int, int>> v(n + 1);
for (int i = 1; i <= n; i++) {
int w, p;
in >> w >> p;
v[i] = {w, p};
}
for (int i = 1; i <= n; i++)
for (int j = g; j >= 0; j--) {
//take
if (j - v[i].first >= 0)
dp[j] = std::max(dp[j], dp[j - v[i].first] + v[i].second);
}
out << dp[g] << '\n';
}