AcWing 8. 二维费用的背包问题
原题链接
中等
作者:
233
,
2019-06-11 15:41:31
,
所有人可见
,
阅读 1033
C++ 代码
//类似01背包问题用滚动数组,那么这个题目就只用二维数组就行了.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(void) {
int N, V, M;//物品种类 背包体积 背包载重
cin >> N >> V >> M;
int v, m, w;//物品 体积 质量 价值
vector<vector<int>>dp(V + 1, vector<int>(M + 1));
for (int i = 1; i <= N; ++i) {
cin >> v >> m >> w;
//每个物品只能用一次
for (int j = V; j >= v; --j) {
for (int k = M; k >= m; --k) {
dp[j][k] = max(dp[j][k], dp[j - v][k - m] + w);
}
}
}
cout << dp[V][M] << endl;
return 0;
}