【Day 30 LeetCode】动态规划DP

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大，这就是标准的背包问题。我们采用动态规划的思想去解决背包问题。
首先需要确定dp数组，有两个维度，物品和重量，dp[i][j]表示0~i的物品在最大容量为j的背包里，最大的价值总和。
然后再确定递推公式，对于物品i，有放入背包和不放入两种选择，所以递推公式为$dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])$
初始化，j=0时任何物品下价值dp[i][0]都是0；i=0时，只有背包容量能装下物品0才能产生价值，dp[0][j]=0,j>=weight[0]。
代码如下：

# include<iostream>
# include<vector>

using namespace std;

int main(){
    int m, w; // m为物品数，w为背包容量
    cin >> m >> w;
    vector<int> weights(m); // 物品重量
    vector<int> values(m); // 物品价值
    for(int i=0; i<m; ++i)
        cin >> weights[i];
    for(int i=0; i<m; ++i)
        cin >> values[i];
    // 创建01背包的dp数组并初始化
    vector<vector<int>> dp(m, vector<int>(w+1));
    for(int i=weights[0]; i<=w; ++i)
        dp[0][i] = values[0];
    // dp方程
    for(int i=1; i<m; ++i){
        for(int j=1; j<=w; ++j){
            if(j >= weights[i])
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i]] + values[i]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[m-1][w] << endl;
    return 0;
}

上面的代码还可以进一步优化空间复杂度，dp数组使用的是二维数组，我们观察dp转移方程$dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])$发现 当前值$dp[i][j]$只与上一行的dp[i-1][j]和dp[i-1][j-weight[i]]有关，分别位于当前值的上方和左上方。因此我们可以只用一个一维数组表示一行的值，然后不断去更新每行的dp数组。
有一个易错点：遍历顺序。如果我们还用上面的遍历顺序，对于二维数组来说肯定是没什么问题，但是对于优化成一维数组来说就有问题了。问题在于上面的代码j是正序遍历，那么我们在当前行i更新dp数组值会先更新j值较小的dp[j]，而dp[j]的更新又可能依赖于上一行的dp[j-weight[i]]，但此时较小的dp[j-weight[i]]是在当前行已被更新，所以正序遍历不行。对于重量j，采用逆序遍历就可以解决这个问题，对于当前dp[j]，dp[j-weight[i]]是未更新的。

# include<iostream>
# include<vector>

using namespace std;

int main(){
    int m, w; // m为物品数，w为背包容量
    cin >> m >> w;
    vector<int> weights(m); // 物品重量
    vector<int> values(m); // 物品价值
    for(int i=0; i<m; ++i)
        cin >> weights[i];
    for(int i=0; i<m; ++i)
        cin >> values[i];
    // 创建01背包的dp数组并初始化
    vector<int>dp(w+1);
    for(int i=weights[0]; i<=w; ++i)
        dp[i] = values[0];
    // dp方程
    for(int i=1; i<m; ++i)
        for(int j=w; j>=weights[i]; --j)
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);

    cout << dp[w] << endl;
    return 0;
}

这题本质上就是将容量为数组和一半的背包填满。背包体积是 数组和的一半，物品、物品价值和物品重量都是数组元素，直接套用01背包代码就好。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = accumulate(nums.begin(), nums.end(), 0); // 数组和
        int n = nums.size();
        // 和为奇数 或 长度为1
        if(s % 2 || n < 2)
            return false;
        s /= 2; // 子集的和
        vector<int> dp(s+1);
        for(int num : nums)
            for(int i=s; i>=num; --i)
                dp[i] = max(dp[i], dp[i-num] + num); // 背包
        return dp[s]==s; 
    }
};