【力扣一刷】代码随想录day44(动态规划part6 - 背包问题专题: 完全背包理论基础、卡码网52、518. 零钱兑换 II、377. 组合总和 Ⅳ )

本文主要是介绍【力扣一刷】代码随想录day44(动态规划part6 - 背包问题专题: 完全背包理论基础、卡码网52、518. 零钱兑换 II、377. 组合总和 Ⅳ ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【完全背包理论基础】

与01背包问题的区别:

1、物品的可取次数:完全背包和01背包问题唯一不同的地方就是,01背包问题的每种物品只能取0次或1次,而完全背包问题的每种物品可以取无限次。

2、遍历滚动数组的顺序:01背包问题每件物品最多取一次,前面取了后面就不能取,所以要逆向遍历书包容量。而完全背包问题可以取无限次,因此是正向遍历,即使前面的书包容量放过物品 i 也可以。遍历第 i 个物品,书包容量为 j 时,不取第 i 个物品,则直接返回旧值dp[ j ],取第 i 个物品时,最大容量为 dp[j - weights[i]] + values[i],其中dp[j - weights[i]]的意思是留足够的空间给需要取的第 i 个物品,再从 0 ~ i 个(包括第 i 个)物品中取,背包容量为j - weights[i]能装下的最大容量。

【52. 携带研究材料(第七期模拟笔试)】

区别:遍历书包容量的时候,是正向遍历。

import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int V = sc.nextInt();int[] weights = new int[N];int[] values = new int[N];for (int i = 0; i < N; i++){weights[i] = sc.nextInt();values[i] = sc.nextInt();}int[] dp = new int[V+1];for (int i = 0; i < N; i++){for (int j = weights[i]; j < V + 1; j++){dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);}}System.out.println(dp[V]);}
}
  • 时间复杂度:O(N×V),N是物品的种类数,V是容量的大小
  • 空间复杂度:O(V)

【518. 零钱兑换 II】中等题

难点:

1、属于完全背包问题,需要正序遍历背包容量,从刚好能装第i个物品的背包容量开始遍历,即初始值 j = coins[i]。

2、要求的是恰好把背包装满的方案数,是放与不放的方案数的叠加,即dp[j] += dp[j - coins[i]];。

3、求的是组合数,外层for遍历的是物品,内层for遍历的是背包容量。

class Solution {public int change(int amount, int[] coins) {int dp[] = new int[amount + 1];dp[0] = 1; // 与题意理解不一样,但是设置amount=0,无论coins输入什么,输出都是1for (int i = 0; i < coins.length; i++){for (int j = coins[i]; j < amount + 1; j++){ // 完全背包:正序遍历dp[j] += dp[j - coins[i]]; // 求的是恰好装满背包的方案数,放和不放的叠加}}return dp[amount];}
}
  • 时间复杂度:O(M×N),M是硬币的种类数,N是amount的数值大小
  • 空间复杂度:O(N)

【377. 组合总和 Ⅳ】中等题

技巧:

1、判断:背包问题 or 完全背包问题?

  • 01背包问题 - 逆序遍历背包容量(不可重复取)
  • 完全背包问题 - 正序遍历背包容量(可重复取)

2、判断:组合数 or 排列数?

  • 求组合数 - 外层for循环遍历物品,内层for遍历背包容量。(物品顺序固定)
  • 求排列数 - 外层for遍历背包容量,内层for循环遍历物品。(物品顺序可变)

3、判断:求最大容量 or 方案数?

  • 求最大容量 dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);  (求最大)
  • 求方案数 dp[j] += dp[j-nums[i]]; (求叠加)

分析:

1、数组中的元素可以重复取,无限次数,属于完全背包问题,正序遍历背包容量

2、顺序不同的序列被视作不同的组合,相当于求的是排列数外层for循环遍历背包容量

3、求的是方案数,使用叠加的公式,记得设置初始值 dp[0] = 1,否则后面全是0。

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;// 求排列数for (int i = 0; i < target + 1; i++){ // 外层for正序遍历书包容量for (int j = 0; j < nums.length; j++){ // 内层for遍历物品if (i >= nums[j]) dp[i] += dp[i - nums[j]]; // 书包容量足够(>=)的情况下才能考虑取}}return dp[target];}
}
  • 时间复杂度:O(M×N),M是target,N是nums数组的元素个数
  • 空间复杂度:O(M)

这篇关于【力扣一刷】代码随想录day44(动态规划part6 - 背包问题专题: 完全背包理论基础、卡码网52、518. 零钱兑换 II、377. 组合总和 Ⅳ )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/965765

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业