【LeetCode】背包问题总结

• 背包问题今天就告一段落了。
  对于多重背包问题，将其转化为01背包问题就能解决，参考如下：
  
  
  示例代码如下：

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();
}

• 背包问题总结
  
• 分类
  1.根据递推公式来分，总体就是两种问题，一是背包问题的原始问题，求装满背包的最小、最大价值；二是完全背包问题中会遇到的组合和排列问题。
  
  2.根据遍历顺序来分，如果都是采用一维滚动数组就有严格的区分，对于01背包问题，为确保物品只使用一次，必须先物品再背包，且背包从大到小；对于完全背包问题，都可以，只是在组合和排列问题上有区分，求组合外层物品内层背包，求排列外层背包内存物品。
  
  为什么组合、排列分别是这个顺序，如下：
  

参考

代码随想录