动态规划/背包问题总结/小结——01背包、完全背包

• 前言
• 动态规划五步法
• 01背包模型
• 完全背包
• 总结

背包问题也属于动态规划问题。

动态规划就是将复杂的大问题转化为一个小问题，然后将小问题转化为更小的容易求解的问题；通过将最小的容易求解的问题求解，进而一步步推导、求解出最后的结果。

背包问题分类：

1. 确定dp数组的含义
2. 确定递推公式
3. 确定初始值
4. 确定遍历顺序
5. 手动推导dp数组的值，是否和程序结果一直

背包的容量为15kg，物品0~4的重量和价值分别为如图所示。
问背包能背的物品最大价值是多少？

每一件物品其实只有两个状态，取或者不取，那么暴力法时间复杂度为O(2^n)。

1. 确定dp数组的含义

dp[i][j]，当背包容量为j时，前 i+1 个物品参与放入背包，此时背包能背的物品的最大价值

2. 确定递推公式

背包容量是个常量。当物品 i 不放入背包时 dp[i][j] = dp[i-1][j]；当物品 i 放入背包时dp[i][i] = dp[i-1][j-wi] + vi；
所以 dp[i][j] = max( dp[i-1][j], dp[i-1][j-wi]+vi )

3. 确定初始值

根据递推公式，需要确定i=0和j=0时的初值

4. 确定遍历顺序

根据5，本题对遍历顺序没有特别的要求

5. dp数组

程序示例

    vector w = {12,1,4,1,2};
    vector v = {4,2,10,1,2};
    int begWight = 15;
    vector> dp(w.size(), vector(begWight+1, 0));
    for (int j=0;j<=begWight; ++j){ //dp数组初始化
        if (w[0] <= j){
            dp[0][j] = v[0];
        }
    }
    //根据递推公式计算dp
    for (int i=1; i
        for (int j=1; j<=begWight; ++j){
            if (j
        for (int j=0; j
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }

优化dp的维度

1. 根据递推公式dp[i][j] = max( dp[i-1][j], dp[i-1][j-wi]+vi )，i取决于i-1，所以可以降二维dp降为一维度。
   此时dp[j]的含义为容量为j的背包能背物品的最大价值。
2. 递推公式变为：dp[j] = max(dp[j], dp[j-wi]+vi)
3. dp数组初始化，全都为0就行
4. 遍历顺序就有了要求，物品i在外部循环，背包的容量j在内部循环。j从大到小

for (int i=0; i              //先遍历物品
    for (int j=begWight; j>=w[i]; --j){      //再遍历背包
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
    }
}

5. dp数组
   当i=0; dp 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
   当i=1; dp 0 2 2 2 2 2 2 2 2 2 2 2 4 6 6 6
   当i=2; dp 0 2 2 2 10 12 12 12 12 12 12 12 12 12 12 12
   当i=3; dp 0 2 3 3 10 12 13 13 13 13 13 13 13 13 13 13
   当i=4; dp 0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15

代码示例

    vector dp(begWight+1, 0);
    // 以下for循环的遍历顺序及j的顺序不能变，思考如果变了会怎么样
    for (int i=0; i               //先遍历物品
        for (int j=begWight; j>=w[i]; --j){       //再遍历背包，从大到小
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
        }
    }
    for (auto c:dp){
        cout << c<< " ";
    }

备注
关于4.一维dp数组的遍历顺序大有讲究，可仔细研究。
当先遍历背包后遍历物品时（j从大到小，i从小到大），每个dp[j]就只会放入一个物品。
当先遍历物品再遍历背包（i从小到大，j从小到大），dp[j]中同一个物品会被放入多次，不符合01背包原则。

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

例如：

1. dp[j]代表容量为j的背包能背物品的最大价值
2. dp[j] = max(dp[j], dp[j-wi]+vi)
3. 对于此题初始化为0就好
4. 对于遍历顺序可小讨论下。完全背包就是物品可重复放入背包，因此遍历顺序为先遍历物品（i有小到大），再遍历背包（j由小到大）。
   其实，先遍历背包再遍历物品也可。
5. 略

程序示例

    vector weight = {1, 3, 4};
    vector value = {15, 20, 30};
    int bagWeight = 4;
    vector dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

01背包模型是所有背包问题的基础。后面的完全背包，多重背包，都是在透彻理解01背包之后的进一步分析，理解了01背包，完全背包、多重背包就非常容易理解。

递推公式：
背包总价值：dp[j] = max(dp[j], dp[j - w[i]] + v[i])
装满背包：dp[j] += dp[j - nums[i]]

遍历顺序：