多重背包
LeetCode上无对应题目，只简单介绍
1. 多重背包例题
题目
有N种物品和一个容量为 V 的背包。第i种物品最多有 M i 件可用，每件耗费的空间是 C i
，价值是 W i 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包和01背包是非常像的， 为什么和01背包像呢？
每件物品最多有 M i 件可用，把 M i 件摊开，其实就是一个01背包问题了。
例如：
背包最大重量为10。
物品为：
| 重量 | 价值 | 数量 | |
| 物品0 | 1 |
15 |
2 |
| 物品1 | 3 |
20 |
3 |
| 物品2 | 4 |
30 |
2 |
问背包能背的物品最大价值是多少？
和如下情况有区别么？
| 重量 | 价值 | 数量 | |
| 物品0 | 1 |
15 |
1 |
| 物品0 | 1 |
15 |
1 |
| 物品1 | 3 |
20 |
1 |
| 物品1 | 3 |
20 |
1 |
| 物品1 | 3 |
20 |
1 |
| 物品2 | 4 |
30 |
1 |
| 物品2 | 4 |
30 |
1 |
毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。
思路
将有多件的物品展开，就可将完全背包转换成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(); return 0; }
