AcWing 2. 01背包问题
原题链接
简单
作者:
DMcxy
,
2023-08-06 09:45:24
,
所有人可见
,
阅读 83
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int N, int V, vector<int>& volumes, vector<int>& values) {
vector<vector<int>> dp(N+1, vector<int>(V+1, 0));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
if (volumes[i-1] <= j) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-volumes[i-1]] + values[i-1]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[N][V];
}
int main() {
int N, V;
cin >> N >> V;
vector<int> volumes(N);
vector<int> values(N);
for (int i = 0; i < N; i++) {
cin >> volumes[i] >> values[i];
}
int max_value = knapsack(N, V, volumes, values);
cout << max_value << endl;
return 0;
}