动态规划Day06(完全背包)
完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是,每种物品有无限件。
同样leetcode上没有纯完全背包问题,都是需要完全背包的各种应用,需要转化成完全背包问题,所以我这里还是以纯完全背包问题进行讲解理论和原理。
每件物品可以放入多次
为什么遍历物品在外层循环,遍历背包容量在内层循环?
01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了,一维dp数组的两个for循环先后循序一定是先遍历物品,再遍历背包容量。
在完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序是无所谓的!
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
518.零钱兑换II(两次)
力扣题目链接(opens new window)
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
- 输入: amount = 5, coins = [1, 2, 5]
- 输出: 4
解释: 有四种方式可以凑成总金额:
- 5=5
- 5=2+2+1
- 5=2+1+1+1
- 5=1+1+1+1+1
看到题目的第一想法
确定可以凑成dp的组合数
但是相同面额的可以重复,使用完全背包
看到代码随想录之后的想法
确定dp数组以及每个下标的含义
dp[j] 为0~i之间能凑成j金额所需要的次数
i为coins下标
确定递推公式
选中coins[i] ,则一共有j-coins[i]种能凑成j
再加上本身的dp[j] ,就知道添加了coins[i]后一共要多少次
dp[j] = dp[j] + dp[j-coins[i]]
确定遍历顺序
可以重复添加物品,则从前往后
dp数组初始化
dp[0]=1为一切的源头,其他都为0
举例推导dp数组
自己实现过程中遇到的困难
我自己写成了 max(dp[j],dp[j-weight[i]]+1) 记混了
要理解组合数,求的是能凑成j的数目,需要累加j-coins[i]
class Solution {public int change(int amount, int[] coins) {//有多少种方式可以凑成对应面额// 确定dp数组以及每个下标的的含义// 能凑成目标金额的最大个数// 确定递推公式// dp[i]+=dp[i-nums[i]]// dp数组初始化// dp[0]=1;其他都为0// 确定遍历顺序// 从前往后,因为可以重复// 手动推导dp数组// 打印dp数组int dp[] = new int[amount+1];dp[0]=1;for(int i=0;i<coins.length;i++){//从前往后for(int j=coins[i];j<=amount;j++){dp[j]=dp[j]+dp[j-coins[i]];}}return dp[amount];}
}
377. 组合总和 Ⅳ
力扣题目链接(opens new window)
难度:中等
给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。
示例:
- 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。
看到题目的第一想法
可以凑成目标正整数的组合的个数。
和零钱兑换II差不多
看到代码随想录之后的想法
确定dp数组以及每个下标的含义
dp[j] 为0~i之间能凑成target所需要的次数
i为nums下标
确定递推公式
选中nums[i] ,则一共有j-nums[i]种能凑成j
再加上本身的dp[j] ,就知道添加了nums[i]后一共要多少次
dp[j] = dp[j] + dp[j-nums[i]]
确定遍历顺序
可以重复添加物品,则从前往后
比如说 (1231) 若可以凑成target
如果先物品后背包 物品1 遍历完后 ,将再也不会遍历到1,之后遍历的是物品2,3,4
所以必须先背包后物品
外层循环是背包容量,物品按照 1 2 3 4的顺序,依次遍历 则 遍历完1,2,3还能遍历回1
dp数组初始化
dp[0]=1为一切的源头,其他都为0
举例推导dp数组
自己实现过程中遇到的困难
需要确认组合数和排列数的区别(看代码注释)
组合数: 不强调顺序,不同顺序的都视为一个集合,必须先物品再背包
排列数: 本题不同的地方在于不同顺序的视为不同集合,则必须先背包再物品
class Solution {public int combinationSum4(int[] nums, int target) {// 组合数:先遍历物品再遍历背包:每次选中一个物品都会遍历所有背包 1号物品一定在2号物品的前面// 排列数:先遍历背包再遍历物品:则每次选中一个背包都会遍历所有物品 每次都是 1号物品,2号物品。。。。 // 第二次 1号物品2号物品 1 2 交替 // 确定dp数组,以及对应下标的含义// 在0~i中满足总和为j的元素的个数,背包重量nums[i] 背包价值nums[i]// 确定递推公式// dp[j]+=dp[j-nums[i]]// dp数组的初始化// dp[0]=1 // 确定遍历顺序// 可以重复 从前往后// 组合数: 不强调顺序,不同顺序的都视为一个集合,必须先物品再背包// 排列数: 本题不同的地方在于不同顺序的视为不同集合,则必须先背包再物品// 手动推导dp数组int[] dp = new int[target+1];dp[0]=1;for(int j=0;j<=target;j++){for(int i=0;i<nums.length;i++){if(j>=nums[i]){dp[j]+=dp[j-nums[i]];}}}return dp[target];}
}
相关文章:
动态规划Day06(完全背包)
完全背包 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同…...
selenium之框架之窗口
...
华为OD机试 - 最小矩阵宽度(Java JS Python C)
题目描述 给定一个矩阵,包含 N * M 个整数,和一个包含 K 个整数的数组。 现在要求在这个矩阵中找一个宽度最小的子矩阵,要求子矩阵包含数组中所有的整数。 输入描述 第一行输入两个正整数 N,M,表示矩阵大小。 接下来 N 行 M 列表示矩阵内容。 下一行包含一个正整数 K…...
嵌入式linux_C应用学习之API函数
1.文件IO 1.1 open打开文件 #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> int open(const char *pathname, int flags); int open(const char *pathname, int flags, mode_t mode);pathname:字符串类型,用于标…...
【ubuntu】docker中如何ping其他ip或外网
docker中如何ping其他ip或外网 示例图: 运行下面命令: docker run -it --namehei busybox看情况需要加权限 sudo,即: sudo docker run -it --namehei busyboxping 外网 ping -c 4 www.baidu.comping 内网 ping -c 4 192.168.…...
【Vue3+Ts项目】硅谷甄选 — 品牌管理+平台属性管理+SPU管理+SKU管理
一、品牌管理模块 1.1 静态模块搭建 使用到element-plus的card、button、table、pagination等组件:src/views/product/trademark/index.vue <template><el-card><!-- 卡片顶部添加品牌按钮 --><el-button type"primary" size&quo…...
计算机图形学流体模拟 blender 渲染脚本
做流体模拟的时候,想要复现别人的成果,但是别人的代码都是每帧输出 ply 格式的文件,渲染部分需要自己完成 看了一下,似乎用 blender 是最简单的,于是记录一下过程中用到的代码 Blender 版本 4.0 批量导入 ply 假设…...
二分图带权最大匹配-KM算法详解
文章目录 零、前言一、红娘再牵线二、二分图带权最大完备匹配2.1二分图带权最大匹配2.2概念2.3KM算法2.3.1交错树2.3.2顶标2.3.3相等子图2.3.4算法原理2.3.5算法实现 三、OJ练习3.1奔小康赚大钱3.2Ants 零、前言 关于二分图:二分图及染色法判定-CSDN博客 关于二分…...
Redis命令 - Sets命令组常用命令
Set集合,无序,一堆不重复值的组合。利用redis提供的set数据结构,可以存储一些集合性的数据。 使用场景:例如,实现如共同关注、共同喜好、二度好友等 1、SADD key member [member …] 向集合中添加一个或者多个成员 …...
DA14531-外设驱动篇-I2C通信应用
文章目录 1.I2C通信应用相关文件2.宏定义列表3.主要函数接口4.应用代码实例1.I2C通信应用相关文件 1)i2c.c和i2c.h(SDK文件) 2)app_I2cProtocol.c和app_I2cProtocol.h(用户应用文件) 2.宏定义列表 宏定义注解I2C_ADDRESSING_7B7-bit 地址I2C_ADDRESSING_10B10-bit 地址…...
Git仓库管理笔记
问题: hint: the same ref. If you want to integrate the remote changes, use Done 解决: 解决方法: 1、先使用pull命令: git pull --rebase origin master 2、再使用push命令: git push -u origin master...
[嵌入式软件][入门篇] 搭建在线仿真平台(STM32)
文章目录 一、注册平台二、创建首个项目三、硬件介绍 一、注册平台 进入官方,进行注册: 在线仿真地址 二、创建首个项目 ① 新建项目 ② 搭建一个电路 ③ 用STM32F103搭建一个简单电路 ④ 进入编码界面 三、硬件介绍 红框是必看文档ÿ…...
设置5台SSH互免的虚拟机服务器配置
搭建一套集群虚拟机,往往都需要互免设置,过程很简单,避免以后再搭建还得网上搜索,我直接将这一个步骤写成笔记,记录下来,方便后续查阅。 步骤如下—— 1、准备五台机器 服务器名字服务器IPhadoop1192.16…...
深信服技术认证“SCCA-C”划重点:交付和运维体系
为帮助大家更加系统化地学习云计算知识,高效通过云计算工程师认证,深信服特推出“SCCA-C认证备考秘笈”,共十期内容。“考试重点”内容框架,帮助大家快速get重点知识。 划重点来啦 *点击图片放大展示 深信服云计算认证ÿ…...
xlua源码分析(五) struct类型优化
xlua源码分析(五) struct类型优化 上一节我们分析了xlua是如何实现lua层访问C#值类型的,其中我们重点提到了xlua默认实现方式下,struct访问的效率问题。实际上,xlua还提供了两种优化的方式,可以大大提高str…...
iptables TEE模块测试小记
概述 因为公司项目需求,需要对服务器特定端口进行流量镜像,各种百度之后,发现TEE的模块,后来一番折腾,发现被转发的机器死活收不到数据,最后tcpdump一通了解到根源,博文记录,用以备…...
facebook广告怎么设置受众人群
在设置Facebook广告受众人群时,你可以遵循以下步骤: 打开广告创建工具,点击页面右上角的箭头并选择“创建广告”。选择广告目标,根据想要实现的目标创建广告。例如,想要让更多用户谈论你的主页和帖子,或者…...
MySQL夯实之路-MVCC机制深入浅出
多版本并发控制(MVCC,multiversion concurrency control) MVCC用更加灵活的方式处理并发,实现了读不加锁,读写不冲突。保证了事务的隔离性(可重复读),避免了不可重复读问题。 数据…...
Java线上问题堆栈排查分析
最近线上出现类似内存溢出问题,需要排查具体原因,记录过程,方便备查。 一、数据抓取 在启动参数中添加参数,可参照以下设置。 参数的作用是在程序发生内存溢出 OutOfMemory 时打印日志,dump下来,方便用工…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...
LangChain【6】之输出解析器:结构化LLM响应的关键工具
文章目录 一 LangChain输出解析器概述1.1 什么是输出解析器?1.2 主要功能与工作原理1.3 常用解析器类型 二 主要输出解析器类型2.1 Pydantic/Json输出解析器2.2 结构化输出解析器2.3 列表解析器2.4 日期解析器2.5 Json输出解析器2.6 xml输出解析器 三 高级使用技巧3…...
【JavaEE】万字详解HTTP协议
HTTP是什么?-----互联网的“快递小哥” 想象我们正在网上购物:打开淘宝APP,搜索“蓝牙耳机”,点击商品图片,然后下单付款。这一系列操作背后,其实有一个看不见的“快递小哥”在帮我们传递信息,…...
电脑定时关机工具推荐
软件介绍 本文介绍一款轻量级的电脑自动关机工具,无需安装,使用简单,可满足定时关机需求。 工具简介 这款关机助手是一款无需安装的小型软件,文件体积仅60KB,下载后可直接运行,无需复杂配置。 使用…...
