题目
例如：
背包最大重量为10。
物品为：
| 重量 | 价值 | 数量 |
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
问背包能背的物品最大价值是多少？
#include<iostream> #include<vector> using namespace std; void test_multi_pack() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; vector<int> nums = {2, 3, 2}; int bagWeight = 10; //***********代码编写区************* //***********代码编写区************* cout << dp[bagWeight] << endl; } int main(){ test_multi_pack(); system("pause"); return 0; }
解题
每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了
#include<iostream> #include<vector> using namespace std; void test_multi_pack() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; vector<int> nums = {2, 3, 2}; int bagWeight = 10; for (int i = 0; i < nums.size(); i++) { while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开 weight.push_back(weight[i]); value.push_back(value[i]); nums[i]--; } } vector<int> dp(bagWeight + 1, 0); for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } for (int j = 0; j <= bagWeight; j++) { cout << dp[j] << " "; } cout << endl; } cout << dp[bagWeight] << endl; } int main(){ test_multi_pack(); system("pause"); return 0; }
