Cod sursa(job #3183861)
Utilizator | Ioja Andrei-Iosif dey44and | Data | 13 decembrie 2023 16:43:37 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 50 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <fstream>
#include <cstring>
#include <cstdlib>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int g[1001], p[1001], n, cap;
int dp[1001][10001]; // d[N][cap]
int main() {
cin >> n >> cap;
for(int i = 1; i <= n; ++i) {
cin >> g[i] >> p[i];
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= cap; ++j) {
dp[i][j] = dp[i - 1][j];
if(j >= g[i])
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - g[i]] + p[i]);
}
}
cout << dp[n][cap];
}