【Day32 LeetCode】动态规划DP Ⅴ 完全背包

一、动态规划DP Ⅴ 完全背包

1、完全背包理论

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大，这就是完全背包问题。完全背包和01背包的区别在于物品的数量是只有一个和无数个，如下图所示。
在这里插入图片描述
下面介绍使用动态规划解决完全背包：
1、首先是dp数组，dp[i][j]表示表示从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。
2、确定递推公式，对于当前值dp[i][j]仍有选与不选物品i两个选择，所以递推公式为 $d p [i] [j] = ma x (d p [i - 1] [j], d p [i] [j - w e i g h t s [i]] + v a l u es [i])$ ，因为在选择物品i的时候，由于物品i是不限个数的，所以是 $d p [i] [j - w e i g h t s [i]]$ 而不是 $d p [i - 1] [j - w e i g h t s [i]]$ 。
3、dp数组初始化：当j=0时，背包装不下任何物品，价值为0；当i=0时，能放下就一直放物品0。
代码如下：

# include<iostream>
# include<vector>

using namespace std;

int main(){
    int n, w;
    cin >> n >> w;
    vector<int> weights(n);
    vector<int> values(n);
    for(int i=0; i<n; ++i)
        cin >> weights[i] >> values[i];
    // dp数组 dp[i][j]表示从下标为[0-i]的物品，每个物品可以取无限次
    // 放进容量为j的背包，价值总和最大是多少
    vector<vector<int>> dp(n, vector<int>(w+1));
    // dp数组初始化
    for(int i=weights[0]; i<=w; ++i)
        dp[0][i] = dp[0][i-weights[0]] + values[0];
    // 循环  dp方程
    for(int i=1; i<n; ++i){
        for(int j=0; j<=w; ++j){
            if(j >= weights[i])
                dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i]] + values[i]);
            else
                dp[i][j] =  dp[i-1][j];
        }
    }
    cout << dp[n-1][w] << endl;
    return 0;
}

空间复杂度优化，由 $d p [i] [j] = ma x (d p [i - 1] [j], d p [i] [j - w e i g h t s [i]] + v a l u es [i])$ 可知dp[i][j]只与dp[i-1][j]和dp[i][j-weights[i]]有关，分别位于其上方和左方，因此可以采用一维数组表示当前行，然后不断更新这一行。由于是与已更新的dp[i][j-weights[i]]有关，所以关于j的遍历顺序是正序的。

# include<iostream>
# include<vector>

using namespace std;

int main(){
    int n, w;
    cin >> n >> w;
    vector<int> weights(n);
    vector<int> values(n);
    for(int i=0; i<n; ++i)
        cin >> weights[i] >> values[i];
    // dp数组 dp[i][j]表示从下标为[0-i]的物品，每个物品可以取无限次
    // 放进容量为j的背包，价值总和最大是多少
    vector<int> dp(w+1);
    // 循环  dp方程
    for(int i=0; i<n; ++i)
        for(int j=weights[i]; j<=w; ++j)
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i]);
    cout << dp[w] << endl;
    return 0;
}

2、零钱兑换Ⅱ 518

这个已知背包容量，且物品数量有无数个，求能够填满背包的方法数。这题与上一篇博客中目标和很相似，都是求填满背包的方法数，但是这里是完全背包，目标和问题是01背包。这里直接套用完全背包的代码框架，需要在dp方程和初始化上稍作修改。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<uint64_t> dp(amount + 1);
        dp[0] = 1;
        for(int i=0; i<coins.size(); ++i)
            for(int j=coins[i]; j<=amount; ++j)
                dp[j] += dp[j-coins[i]];
        return dp[amount];
    }
};

3、组合总和 Ⅳ 377

这题也是已知背包容量，且物品数量有无数个，求能够填满背包的方法的排列数。这题和上一题零钱兑换Ⅱ的区别在于这题是求排列，关注结果的顺序，而上一题是求组合，不关注结果的顺序。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。这样得到的方法是按照物品的顺序进行排列，通过循环人为规定一个顺序。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。这样可以遍历到所有的顺序。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<uint64_t> dp(target + 1);
        dp[0] = 1;
        for(int j=1; j<=target; ++j)
            for(int i=0; i<nums.size(); ++i)
                if(j >= nums[i])
                    dp[j] += dp[j-nums[i]];
        return dp[target];
    }
};

4、爬楼梯 70

这里我们从01背包的视角来重新分析这道dp简单题。以n阶楼顶为背包，每次走1~m步为物品，且物品不限次数，求装满背包有多少种方法，方法内物品在意顺序，这是个排列结果，所以需要先遍历背包，后遍历物品。

# include<iostream>
# include<vector>

using namespace std;

int main(){
    int m, n;
    cin >> n >> m;
    vector<int> dp(n + 1);
    dp[0] = 1;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            if(i-j >= 0)
                dp[i] += dp[i-j];
    cout << dp[n] << endl;
    return 0;
}