【LeetCode】背包问题总结

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

void test_multi_pack() {
    vector weight = {1, 3, 4};
    vector value = {15, 20, 30};
    vector 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 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背包问题，为确保物品只使用一次，必须先物品再背包，且背包从大到小；对于完全背包问题，都可以，只是在组合和排列问题上有区分，求组合外层物品内层背包，求排列外层背包内存物品。
  
  为什么组合、排列分别是这个顺序，如下：
  

代码随想录