积极加强网站建设,关键词seo排名优化,如何在手机上搭建网站,知识付费网站建设文章目录 完全背包518. 零钱兑换 II (求组合方法数)思路分析代码实现思考总结 377. 组合总和 Ⅳ (求排列方法数)思路分析代码实现思考总结 完全背包
完全背包和01背包问题唯一不同的地方就是#xff0c;每种物品有无限件。 依然举这个例子#xff1a;
背包最大重量为4。
物… 文章目录 完全背包518. 零钱兑换 II (求组合方法数)思路分析代码实现思考总结 377. 组合总和 Ⅳ (求排列方法数)思路分析代码实现思考总结 完全背包
完全背包和01背包问题唯一不同的地方就是每种物品有无限件。 依然举这个例子
背包最大重量为4。
物品为
重量价值物品0115物品1320物品2430
每件商品都有无限个 问背包能背的物品最大价值是多少
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]都是经过计算的就可以了。 完整代码
// 先遍历物品在遍历背包
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();
} 518. 零钱兑换 II (求组合方法数)
题目链接 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1: 输入: amount 5, coins [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 55 5221 52111 511111
示例 2: 输入: amount 3, coins [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。
示例 3: 输入: amount 10, coins [10] 输出: 1
注意你可以假设 0 amount (总金额) 5000 1 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]];
这个递推公式在这篇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数组
输入: amount 5, coins [1, 2, 5] dp状态图如下
代码实现
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount1,0);dp[0]1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}return dp[amount];}
};思考总结
难点在于遍历顺序
在求装满背包有几种方案的时候认清遍历顺序是非常关键的。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
和下一道题好好对比。 377. 组合总和 Ⅳ (求排列方法数)
题目链接 给定一个由正整数组成且不存在重复数字的数组找出和为给定目标正整数的组合的个数。
示例: 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。
思路分析
元素相同顺序不同的组合算两个组合其实就是求排列 其本质是本题求的是排列总和而且仅仅是求排列总和的个数并不是把所有的排列都列出来。 如果本题要把排列都列出来的话只能使用回溯算法爆搜。
动规五部曲分析如下
确定dp数组以及下标的含义
dp[i]: 凑成目标正整数为i的排列个数为dp[i]
确定递推公式
在494. 目标和和518.零钱兑换II中我们已经讲过了求装满背包有几种方法递推公式一般都是dp[j] dp[j - nums[i]];
本题也一样。
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数组
我们再来用示例中的例子推导一下
代码实现
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target1,0);dp[0]1;for(int j0;jtarget;j){for(int i0;inums.size();i){//C测试用例有两个数相加超过int的数据所以需要在if里加上dp[j] INT_MAX - dp[j - nums[i]]。if(jnums[i]dp[j] INT_MAX - dp[j - nums[i]]) dp[j]dp[j-nums[i]]; }}return dp[target];}
};思考总结
求装满背包有几种方法递归公式都是一样的没有什么差别但关键在于遍历顺序
