【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两个选择，所以 递推公式为 $dp[i][j]=max(dp[i-1][j],dp[i][j-weights[i]]+values[i])$，因为在选择物品i的时候，由于物品i是不限个数的，所以是$dp[i][j-weights[i]]$而不是$dp[i-1][j-weights[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]);elsedp[i][j] =  dp[i-1][j];}}cout << dp[n-1][w] << endl;return 0;
}

空间复杂度优化，由$dp[i][j]=max(dp[i-1][j],dp[i][j-weights[i]]+values[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;
}

二、写在后面

第一题是完全背包的经典问题，求装满背包的最大价值。
对于第二、三题，需要清楚 遍历顺序，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。
第四题爬楼梯问题其实就是完全背包问题，与第三题组合总和Ⅳ一模一样。