6成都网站建设,怎样自做网站,网页制作培训的课程,企业网站建设的必要性及维护第九章 动态规划part06完全背包理论基础完全背包C测试代码总结518. 零钱兑换 II题目描述思路总结377. 组合总和 Ⅳ题目描述思路总结完全背包理论基础
参考#xff1a;https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%…
第九章 动态规划part06完全背包理论基础完全背包C测试代码总结518. 零钱兑换 II题目描述思路总结377. 组合总和 Ⅳ题目描述思路总结完全背包理论基础
参考https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html
完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是每种物品有无限件。
同样leetcode上没有纯完全背包问题都是需要完全背包的各种应用需要转化成完全背包问题所以我这里还是以纯完全背包问题进行讲解理论和原理。
在下面的讲解中我依然举这个例子
背包最大重量为4。
物品为 每件商品都有无限个
问背包能背的物品最大价值是多少
01背包和完全背包唯一不同就是体现在遍历顺序上所以本文就不去做动规五部曲了我们直接针对遍历顺序经行分析
首先在回顾一下01背包的核心代码
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]);}
}我们知道01背包内嵌的循环是从大到小遍历为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的所以要从小到大去遍历即
// 先遍历物品再遍历背包
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]);}
}dp状态图如下 其实还有一个很重要的问题为什么遍历物品在外层循环遍历背包容量在内层循环
这个问题很多题解关于这里都是轻描淡写就略过了大家都默认 遍历物品在外层遍历背包容量在内层好像本应该如此一样那么为什么呢
难道就不能遍历背包容量在外层遍历物品在内层
01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了一维dp数组的两个for循环先后循序一定是先遍历物品再遍历背包容量。
在完全背包中对于一维dp数组来说其实两个for循环嵌套顺序是无所谓的
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
遍历物品在外层循环遍历背包容量在内层循环状态如图 遍历背包容量在外层循环遍历物品在内层循环状态如图 看了这两个图大家就会理解完全背包中两个for循环的先后循序都不影响计算dp[j]所需要的值这个值就是下标j之前所对应的dp[j]。
先遍历背包在遍历物品代码如下
// 先遍历背包再遍历物品
for(int j 0; j bagWeight; j) { // 遍历背包容量for(int i 0; i weight.size(); i) { // 遍历物品if (j - weight[i] 0) dp[j] max(dp[j], dp[j - weight[i]] value[i]);}cout endl;
}C测试代码
完整的C测试代码如下
// 先遍历物品在遍历背包
void test_CompletePack() {vectorint weight {1, 3, 4};vectorint value {15, 20, 30};int bagWeight 4;vectorint 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]);}}cout dp[bagWeight] endl;
}
int main() {test_CompletePack();
}// 先遍历背包再遍历物品
void test_CompletePack() {vectorint weight {1, 3, 4};vectorint value {15, 20, 30};int bagWeight 4;vectorint dp(bagWeight 1, 0);for(int j 0; j bagWeight; j) { // 遍历背包容量for(int i 0; i weight.size(); i) { // 遍历物品if (j - weight[i] 0) dp[j] max(dp[j], dp[j - weight[i]] value[i]);}}cout dp[bagWeight] endl;
}
int main() {test_CompletePack();
}总结
细心的同学可能发现全文我说的都是对于纯完全背包问题其for循环的先后循环是可以颠倒的
但如果题目稍稍有点变化就会体现在遍历顺序上。
如果问装满背包有几种方式的话 那么两个for循环的先后顺序就有很大区别了而leetcode上的题目都是这种稍有变化的类型。
这个区别我将在后面讲解具体leetcode题目中给大家介绍因为这块如果不结合具题目单纯的介绍原理估计很多同学会越看越懵
别急下一篇就是了哈哈
最后又可以出一道面试题了就是纯完全背包要求先用二维dp数组实现然后再用一维dp数组实现最后在问两个for循环的先后是否可以颠倒为什么 这个简单的完全背包问题估计就可以难住不少候选人了。
518. 零钱兑换 II
题目链接518. 零钱兑换 II 参考https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html
题目描述
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount 5, coins [1, 2, 5]输出: 4
解释: 有四种方式可以凑成总金额:
55522152111511111
示例 2:
输入: amount 3, coins [2]输出: 0解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount 10, coins [10]输出: 1
注意你可以假设
0 amount (总金额) 50001 coin (硬币面额) 5000硬币种类不超过 500 种结果符合 32 位符号整数
思路
这是一道典型的背包问题一看到钱币数量不限就知道这是一个完全背包。
但本题和纯完全背包不一样纯完全背包是凑成背包最大价值是多少而本题是要求凑成总金额的物品组合个数
注意题目描述中是凑成总金额的硬币组合数为什么强调是组合数呢
例如示例一
5 2 2 1
5 2 1 2
这是一种组合都是 2 2 1。
如果问的是排列数那么上面就是两种排列了。
组合不强调元素之间的顺序排列强调元素之间的顺序。 其实这一点我们在讲解回溯算法专题的时候就讲过了哈。
那我为什么要介绍这些呢因为这和下文讲解遍历顺序息息相关!
回归本题动规五步曲来分析如下
确定dp数组以及下标的含义
dp[j]凑成总金额j的货币组合数为dp[j]
确定递推公式
dp[j] 就是所有的dp[j - coins[i]]考虑coins[i]的情况相加。
所以递推公式dp[j] dp[j - coins[i]];
这个递推公式大家应该不陌生了我在讲解01背包题目的时候在这篇494. 目标和 中就讲解了求装满背包有几种方法公式都是dp[j] dp[j - nums[i]];
dp数组如何初始化 首先dp[0]一定要为1dp[0] 1是 递归公式的基础。如果dp[0] 0 的话后面所有推导出来的值都是0了。
那么 dp[0] 1 有没有含义其实既可以说 凑成总金额0的货币组合数为1也可以说 凑成总金额0的货币组合数为0好像都没有毛病。
但题目描述中也没明确说 amount 0 的情况结果应该是多少。
这里我认为题目描述还是要说明一下因为后台测试数据是默认amount 0 的情况组合数为1的。
下标非0的dp[j]初始化为0这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
dp[0]1还说明了一种情况如果正好选了coins[i]后也就是j-coins[i] 0的情况表示这个硬币刚好能选此时dp[0]为1表示只选coins[i]存在这样的一种选法。
确定遍历顺序
本题中我们是外层for循环遍历物品钱币内层for遍历背包金钱总额还是外层for遍历背包金钱总额内层for循环遍历物品钱币呢
完全背包的两个for循环的先后顺序都是可以的。
但本题就不行了
因为纯完全背包求得装满背包的最大价值是多少和凑成总和的元素有没有顺序没关系即有顺序也行没有顺序也行
而本题要求凑成总和的组合数元素之间明确要求没有顺序。
所以纯完全背包是能凑成总和就行不用管怎么凑的。
本题是求凑出来的方案个数且每个方案个数是为组合数。
那么本题两个for循环的先后顺序可就有说法了。
我们先来看 外层for循环遍历物品钱币内层for遍历背包金钱总额的情况。
代码如下
for (int i 0; i coins.size(); i) { // 遍历物品for (int j coins[i]; j amount; j) { // 遍历背包容量dp[j] dp[j - coins[i]];}
}假设coins[0] 1coins[1] 5。
那么就是先把1加入计算然后再把5加入计算得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数
如果把两个for交换顺序代码如下
for (int j 0; j amount; j) { // 遍历背包容量for (int i 0; i coins.size(); i) { // 遍历物品if (j - coins[i] 0) dp[j] dp[j - coins[i]];}
}背包容量的每一个值都是经过 1 和 5 的计算包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数
可能这里很多同学还不是很理解建议动手把这两种方案的dp数组数值变化打印出来对比看一看实践出真知
举例推导dp数组
输入: amount 5, coins [1, 2, 5] dp状态图如下 最后红色框dp[amount]为最终结果。
以上分析完毕C代码如下
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount 1, 0);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];}
};总结
本题的递推公式其实我们在494. 目标和 中就已经讲过了而难点在于遍历顺序
在求装满背包有几种方案的时候认清遍历顺序是非常关键的。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
可能说到排列数录友们已经有点懵了后面Carl还会安排求排列数的题目到时候在对比一下大家就会发现神奇所在
377. 组合总和 Ⅳ
题目链接377. 组合总和 Ⅳ 参考https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html
题目描述
难度中等
给定一个由正整数组成且不存在重复数字的数组找出和为给定目标正整数的组合的个数。
示例:
nums [1, 2, 3]target 4所有可能的组合为 (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意顺序不同的序列被视作不同的组合。
因此输出为 7。
思路
本题题目描述说是求组合但又说是可以元素相同顺序不同的组合算两个组合其实就是求排列
弄清什么是组合什么是排列很重要。
组合不强调顺序(1,5)和(5,1)是同一个组合。
排列强调顺序(1,5)和(5,1)是两个不同的排列。
大家在公众号里学习回溯算法专题的时候一定做过这两道题目回溯算法39.组合总和和回溯算法40.组合总和II 会感觉这两题和本题很像
但其本质是本题求的是排列总和而且仅仅是求排列总和的个数并不是把所有的排列都列出来。
如果本题要把排列都列出来的话只能使用回溯算法爆搜。
动规五部曲分析如下
确定dp数组以及下标的含义
dp[i]: 凑成目标正整数为i的排列个数为dp[i]
确定递推公式
dp[i]考虑nums[j]可以由 dp[i - nums[j]]不考虑nums[j] 推导出来。
因为只要得到nums[j]排列个数dp[i - nums[j]]就是dp[i]的一部分。
求装满背包有几种方法递推公式一般都是dp[i] dp[i - nums[j]];
dp数组如何初始化
因为递推公式dp[i] dp[i - nums[j]]的缘故dp[0]要初始化为1这样递归其他dp[i]的时候才会有数值基础。
至于dp[0] 1 有没有意义呢
其实没有意义所以我也不去强行解释它的意义了因为题目中也说了给定目标值是正整数 所以dp[0] 1是没有意义的仅仅是为了推导递推公式。
至于非0下标的dp[i]应该初始为多少呢
初始化为0这样才不会影响dp[i]累加所有的dp[i - nums[j]]。
确定遍历顺序
个数可以不限使用说明这是一个完全背包。
得到的集合是排列说明需要考虑元素之间的顺序。
本题要求的是排列那么这个for循环嵌套的顺序可以有说法了。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
如果把遍历nums物品放在外循环遍历target的作为内循环的话举一个例子计算dp[4]的时候结果集只有 {1,3} 这样的集合不会有{3,1}这样的集合因为nums遍历放在外层3只能出现在1后面
所以本题遍历顺序最终遍历顺序target背包放在外循环将nums物品放在内循环内循环从前到后遍历。
举例来推导dp数组
我们再来用示例中的例子推导一下 如果代码运行处的结果不是想要的结果就把dp[i]都打出来看看和我们推导的一不一样。
以上分析完毕C代码如下
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target 1, 0);dp[0] 1;for (int i 0; i target; i) { // 遍历背包for (int j 0; j nums.size(); j) { // 遍历物品if (i - nums[j] 0 dp[i] INT_MAX - dp[i - nums[j]]) {dp[i] dp[i - nums[j]];}}}return dp[target];}
};C测试用例有两个数相加超过int的数据所以需要在if里加上dp[i] INT_MAX - dp[i - num]。
总结
求装满背包有几种方法递归公式都是一样的没有什么差别但关键在于遍历顺序
本题与动态规划518.零钱兑换II就是一个鲜明的对比一个是求排列一个是求组合遍历顺序完全不同。
如果对遍历顺序没有深度理解的话做这种完全背包的题目会很懵逼即使题目刷过了可能也不太清楚具体是怎么过的。
