站长之家网页模板下载,最全的百度网盘搜索引擎,电商网站建设题库,龙岩会员系统小程序定制开发代码随想录训练营Day44 | Leetcode 518、377 一、完全背包问题1、完全背包与01背包的区别 二、518 零钱兑换II三、377 组合总和IV 一、完全背包问题
1、完全背包与01背包的区别
第一#xff0c;物品的有限与无限#xff1b; 01背包#xff1a;物品是有限的。#xff08;每… 代码随想录训练营Day44 | Leetcode 518、377 一、完全背包问题1、完全背包与01背包的区别 二、518 零钱兑换II三、377 组合总和IV 一、完全背包问题
1、完全背包与01背包的区别
第一物品的有限与无限 01背包物品是有限的。每个物品只能被选择一次放入背包 完全背包物品是无限的即可以重复选择某物品装入背包
第二遍历顺序存在不同 01背包遍历背包容量时是从大到小的倒序遍历目的是保证每个物品仅被添加一次 完全背包添加物品是可以是多次因此需要从小到大遍历即按背包容量顺序遍历
第三遍历物品和背包容量的先后顺序。 01背包使用一维dp数组时必须要求先遍历物品再遍历背包容量二维dp数组的遍历顺序没有要求 完全背包使用一维dp数组的遍历顺序是没有要求的但是这仅仅对于纯完全背包问题在某些具体问题上遍历顺序是有要求的。
二、518 零钱兑换II
题目链接518 零钱兑换II
核心硬币物品有无限个且背包最大容量是amount可以建模成完全背包问题。 dp[j]装满背包容量j时的不同方法数可知求解的是组合数即递推公式是累加。 注意组合问题先遍历物品再遍历背包容量因为无排列顺序要求保证不同顺序的组合只计数一次排列问题先遍历背包容量再遍历物品因为排列存在顺序要求即不同顺序的排列都需要计数。 int change(int amount, vectorint coins) {//完全背包问题且给定背包容量amount求解组合方法数累加vectorint dp(amount1,0);dp[0]1; //初始化必须为1for(int i0;icoins.size();i){//组合问题先遍历物品即硬币值再遍历背包容量jfor(int jcoins[i];jamount;j)dp[j]dp[j-coins[i]]; //组合需要累加}return dp[amount];}三、377 组合总和IV
题目链接377 组合总和IV
核心给定背包容量target数组元素可以使用无限次故可以建模成完全背包问题。 由于不同顺序的组合属于不同的组合个数即考虑排列顺序问题因此实质是求解排列。 排列问题先遍历背包容量再遍历物品。 int combinationSum4(vectorint nums, int target) {//完全背包问题且给定背包容量target求解不同方法数表面看似组合实际却是排列vectorint dp(target1,0); //dp[j]:装满容量j的背包的不同方法数dp[0]1; //初始化for(int j0;jtarget;j){//排列问题先遍历背包容量再遍历物品for(int i0;inums.size();i){//遍历物品时背包容量必须大于物品重量且考虑数据溢出情况if(jnums[i] dp[j]INT_MAX-dp[j-nums[i]])dp[j]dp[j-nums[i]];}}return dp[target];}
