代码随想录算法训练营第38天—动态规划06 | ● 完全背包 ● *518. 零钱兑换 II ● 377. 组合总和 Ⅳ
完全背包
视频讲解:https://www.bilibili.com/video/BV1uK411o7c9
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背包的解法相同,以下以一维数组解法为例,其和01背包的解法主要有两点不同:
- 一是内层for循环从逆向遍历改为正向遍历,因为完全背包里的每个物品是可以多次放入背包中的
- 二是对于纯完全背包问题,内外层for循环是可以颠倒的,也就是说先遍历物品和先遍历背包容量都可以,其中为什么先遍历背包容量也可以呢?这样不会导致过程中某些dp[j]依赖于了下一个物品的dp[j]吗?其实是没关系的,无论是否依赖了下一个物品,我们最终得到的最后的那个结果值都不会变,也就是说过程中即便发生了变化,结果仍然是正确的。但从理论上来讲,其实还是应该先遍历物品,这样每一步都是正确的,不会产生困惑
- 而对于完全背包应用类题目里的求装满背包有多少种情况的问题,内外层循环的顺序有如下讲究
- 先遍历物品,再遍历背包容量,得到的结果是组合数——因为此时在不同种背包容量的情况里,都是先放进物品1再放进物品2,不会出现先放2再放1的情况,此时得到的组合之间不会出现顺序不同、元素相同的情况
- 先遍历背包容量,再遍历物品,得到的结果是排列数——因为此时在背包容量递增的过程中,物品1和物品2放入的先后顺序不一定,可能先放了1也可能先放了2,因此集合之间会出现顺序不同、元素相同的情况,也就是得到的结果是排列数
- 而对于完全背包应用类题目里的求装满背包有多少种情况的问题,内外层循环的顺序有如下讲究
- 滚动数组(一维数组解法)
- 动规五部曲
- 一维dp数组dp[j]
- 其中j代表背包的容量,dp值代表对应的最大价值
- 递推公式
- 当前 j 对应的最大价值为
装第i个物品和不装第i个物品两种情况里的较大值 - 其中装第i个物品对应的dp值为
dp[j - weight[i]] + value[i],weight[i]表示第i个物品的重量,value[i]代表第i个物品的价值 - 不装第i个物品对应的dp值为dp[j]
- 即
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
- 当前 j 对应的最大价值为
- 一维dp数组的初始化
- 全部初始化为0即可
- 遍历顺序
- 对于纯完全背包类问题,内外层for循环可以互相颠倒,但是二者的遍历顺序均是从前往后
- 无需打印
- 一维dp数组dp[j]
- 代码书写问题
- 无
- 动规五部曲
# 一维数组解法
# m种物品,背包容量为n,每个物品的重量和价值分别保存在weight和value里
dp = [0] * (n + 1)
for i in range(1, m):for j in range(1, n + 1):if (j - weight[i]) >= 0:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp[-1])
*518. 零钱兑换 II
视频讲解:https://www.bilibili.com/video/BV1KM411k75j
https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html
- 考点
- 动态规划
- 完全背包
- 组合和排列(下一道题就是排列问题)
- 我的思路
- 思路就是给一个背包和给多个物品,问装满背包有多少种组合(每个物品可以重复拿取)
- 视频讲解关键点总结
- 我的思路没有问题,需要注意的是,不同的内外循环顺序会带来不同的结果,一种计算的是组合数,一种计算的是排列数(相同的元素,不同的顺序也视为不同)
- 先遍历物品,再遍历背包容量,得到的结果是组合数——因为此时在不同种背包容量的情况里,都是先放进物品1再放进物品2,不会出现先放2再放1的情况,此时得到的组合之间不会出现顺序不同、元素相同的情况
- 先遍历背包容量,再遍历物品,得到的结果是排列数——因为此时在背包容量递增的过程中,物品1和物品2放入的先后顺序不一定,可能先放了1也可能先放了2,因此集合之间会出现顺序不同、元素相同的情况,也就是得到的结果是排列数
- 我的思路没有问题,需要注意的是,不同的内外循环顺序会带来不同的结果,一种计算的是组合数,一种计算的是排列数(相同的元素,不同的顺序也视为不同)
- 我的思路的问题
- 无
- 代码书写问题
- 无
- 可执行代码
class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0] * (amount + 1)dp[0] = 1for i in range(len(coins)):for j in range(1, amount + 1):if j >= coins[i]:dp[j] += dp[j - coins[i]]return dp[-1]
377. 组合总和 Ⅳ
视频讲解:https://www.bilibili.com/video/BV1V14y1n7B6
https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html
- 考点
- 动态规划
- 完全背包
- 组合和排列
- 我的思路
- 思路就是给一个背包和给多个物品,问装满背包有多少种排列(每个物品可以重复拿取)
- 视频讲解关键点总结
- 我的思路没有问题,需要注意的是,不同的内外循环顺序会带来不同的结果,一种计算的是组合数,一种计算的是排列数(相同的元素,不同的顺序也视为不同)
- 先遍历物品,再遍历背包容量,得到的结果是组合数——因为此时在不同种背包容量的情况里,都是先放进物品1再放进物品2,不会出现先放2再放1的情况,此时得到的组合之间不会出现顺序不同、元素相同的情况
- 先遍历背包容量,再遍历物品,得到的结果是排列数——因为此时在背包容量递增的过程中,物品1和物品2放入的先后顺序不一定,可能先放了1也可能先放了2,因此集合之间会出现顺序不同、元素相同的情况,也就是得到的结果是排列数
- 我的思路没有问题,需要注意的是,不同的内外循环顺序会带来不同的结果,一种计算的是组合数,一种计算的是排列数(相同的元素,不同的顺序也视为不同)
- 我的思路的问题
- 无
- 代码书写问题
- 无
- 可执行代码
class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [0] * (target + 1)dp[0] = 1for j in range(1, target + 1):for i in range(len(nums)):if j >= nums[i]:dp[j] += dp[j - nums[i]]return dp[-1]
相关文章:
代码随想录算法训练营第38天—动态规划06 | ● 完全背包 ● *518. 零钱兑换 II ● 377. 组合总和 Ⅳ
完全背包 视频讲解:https://www.bilibili.com/video/BV1uK411o7c9 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件物品和一个最多能…...
C语言每日一题(63)复写零
题目链接 力扣网 1089 复写零 题目描述 给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。 注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不…...
ElasticSearch聚合查询
数据准备 索引创建 PUT product {"mappings": {"properties": {"createtime": {"type": "date"},"desc": {"type": "text","fields": {"keyword": {"type": …...
【毕设级项目】基于AI技术的多功能消防机器人(完整工程资料源码)
基于AI技术的多功能消防机器人演示效果 竞赛-基于AI技术的多功能消防机器人视频演示 前言: 随着“自动化、智能化”成为数字时代发展的关键词,机器人逐步成为社会经济发展的重要主体之一,“机器换人”成为发展的全新趋势和时代潮流。在可预见…...
【一】【设计模式】类关系UML图
1. 继承(Generalization) 继承是对象间的一种层次关系,允许子类继承并扩展父类的功能。 UML线:带有空心箭头的直线,箭头指向基类(父类)。 class Parent {public void parentMethod() {System.…...
【DevOps基础篇】容器化架构基础设施监控方案
【DevOps基础篇】容器化架构基础设施监控方案 目录 【DevOps基础篇】容器化架构基础设施监控方案要监视什么不同监控系统方案比较1. Datadog2. Prometheus3. ELK(Elasticsearch、Logstash、Kibana)4. Sysdig5. 自行打造!如何选择总结推荐超级课程: Docker快速入门到精通 当…...
【QT】文件流操作(QTextStream/QDataStream)
文本流/数据流(二级制格式) 文本流 (依赖平台,不同平台可能乱码)涉及文件编码 #include <QTextStream>操作的都是基础数据类型:int float string //Image Qpoint QRect就不可以操作 需要下面的 …...
CentOS 7 devtoolset编译addressSanitizer版本失败的问题解决
在我的一个Cent OS7开发环境中,按https://yeyongjin.blog.csdn.net/article/details/134178420的方法升级GCC版本到8.3.1。 这两天,要用Google的addressSanitizer检验内存问题,加上编译参数后,却发现编译不通过。configure时直接退…...
ubuntu2004桌面系统英伟达显卡驱动安装方法
#如何查看显卡型号 lspci | grep -i vga#----output------ 01:00.0 VGA compatible controller: NVIDIA Corporation Device 1f06 (rev a1)根据 Device 后的 值 进入网站查询 pci-ids.ucw.cz/mods/PC/10de?actionhelp?helppci #根据显卡型号,下载对应系统的驱动…...
Java通过Excel批量上传数据!!!
一、首先在前端写一个上传功能。 <template><!-- 文件上传 --><el-upload class"upload-demo" drag action"" :on-change"onChange" :auto-upload"false"><el-icon class"el-icon--upload"><up…...
【PyQT/Pysider】控件背景渐变
默认渐变配色说明 background-color: qlineargradient(spread:pad, x1:0, y1:0, x2:1, y2:0, stop:0 rgba(255, 178, 102, 255), stop:0.55 rgba(235, 148, 61, 255), stop:0.98 rgba(0, 0, 0, 255), stop:1 rgba(0, 0, 0, 0));这段样式表使用了qlineargradient函数来创建…...
ChatGPT-4 VS 文心一言4.0
在线体验 地址(含 gpt 3.5 / 4.0,文心 3.5 / 4.0):https://chat.tool4j.com 点击访问 文心一言和ChatGPT-4都是非常强大的自然语言处理模型,它们都能够在对话系统和其他NLP应用中发挥巨大的作用。然而,它们…...
MYSQL------从概述到DQL
数据库(数据管理,数据存储的仓库) 数据库管理系统(操纵和管理数据库的大型软件) SQL是操作关系型的编程语言,是一套标准 MySQL下载安装完成以后,可以进行启动和停止操作,对于启动和停…...
MATLAB算法实战应用案例精讲-【图像处理】图像识别(基础篇)(二)
目录 数字图像处理基本知识 传统图像处理方法进行瑕疵检测 传统算法方向的选择...
Leetcode 3.12
leetcode hot 100 链表1.两两交换链表中的节点2.随机链表的复制3.排序链表 链表 1.两两交换链表中的节点 两两交换链表中的节点 1.必须要设置一个dummy (temp) 结点2.保存第二个节点3.先让第一个节点指向第三个节点4.再让第二个节点指向第一个节点5.最后让dummy指向第二个节点…...
【天池课堂】零基础入门数据挖掘-课程汇总
写在前面: 如果你现在很迷茫,但是又对数据挖掘感兴趣,建议先看看以下两个视频直播,两位大佬亲身讲述自己和数据挖掘的前世今生。 《如何入门数据挖掘竞赛》 鱼遇雨欲语与余。天池明星选手,武汉大学硕士,天…...
表单进阶(3)-上传文件和隐藏字段
上传文件:<input type"file"> 隐藏字段:<input type"hidden" name"" id"" value"带给后端的信息"> 禁用disabled:<button disabled"disabled">注册</bu…...
LLM(大语言模型)常用评测指标-MAP@R
MAPR (Mean Average Precision at R) 是一种用于评估信息检索系统或排序模型效果的评价指标。它特别适用于那些返回一组相关结果的情况,例如搜索引擎或推荐系统。这里的“R”代表返回的相关结果的数量。MAPR 考虑了结果的排名和相关性两个因素。 计算方法 计算平…...
腾讯面经学习笔记
💖 前言 👩🏫 参考地址 💖 操作系统 1. 进程和线程的区别 本质区别 进程是操作系统资源分配的基本单位线程是任务调度和执行的基本单位 开销方面 每个进程都有独立的代码和数据空间(程序上下文)&#…...
北京某中厂凉经
3月12号 大二想着找一份暑假面试,然后就海投。北京某上市公司给了面试,这也是我的第一个面试,听面试官最后的话大概是挂了。 大概回忆一下当时面试的部分内容吧,虽然已经过去一两小时的,而且我属于那种一面完就忘的差…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...
