当前位置: 首页 > news >正文

【Day32 LeetCode】动态规划DP Ⅴ 完全背包

一、动态规划DP Ⅴ 完全背包

1、完全背包理论

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大,这就是完全背包问题。完全背包和01背包的区别在于物品的数量是只有一个和无数个,如下图所示。
在这里插入图片描述
下面介绍使用动态规划解决完全背包:
1、首先是dp数组,dp[i][j]表示表示从下标为[0-i]的物品,每个物品可以取无限次,放进容量为j的背包,价值总和最大是多少
2、确定递推公式,对于当前值dp[i][j]仍有选与不选物品i两个选择,所以 递推公式为 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − w e i g h t s [ i ] ] + v a l u e s [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i]] + values[i]) dp[i][j]=max(dp[i1][j],dp[i][jweights[i]]+values[i]),因为在选择物品i的时候,由于物品i是不限个数的,所以是 d p [ i ] [ j − w e i g h t s [ i ] ] dp[i][j-weights[i]] dp[i][jweights[i]]而不是 d p [ i − 1 ] [ j − w e i g h t s [ i ] ] dp[i-1][j-weights[i]] dp[i1][jweights[i]]
3、dp数组初始化:当j=0时,背包装不下任何物品,价值为0;当i=0时,能放下就一直放物品0。
代码如下:

# include<iostream>
# include<vector>using namespace std;int main(){int n, w;cin >> n >> w;vector<int> weights(n);vector<int> values(n);for(int i=0; i<n; ++i)cin >> weights[i] >> values[i];// dp数组 dp[i][j]表示从下标为[0-i]的物品,每个物品可以取无限次// 放进容量为j的背包,价值总和最大是多少vector<vector<int>> dp(n, vector<int>(w+1));// dp数组初始化for(int i=weights[0]; i<=w; ++i)dp[0][i] = dp[0][i-weights[0]] + values[0];// 循环  dp方程for(int i=1; i<n; ++i){for(int j=0; j<=w; ++j){if(j >= weights[i])dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i]] + values[i]);elsedp[i][j] =  dp[i-1][j];}}cout << dp[n-1][w] << endl;return 0;
}

空间复杂度优化,由 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − w e i g h t s [ i ] ] + v a l u e s [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i]] + values[i]) dp[i][j]=max(dp[i1][j],dp[i][jweights[i]]+values[i])可知dp[i][j]只与dp[i-1][j]和dp[i][j-weights[i]]有关,分别位于其上方和左方,因此可以采用一维数组表示当前行,然后不断更新这一行。由于是与已更新的dp[i][j-weights[i]]有关,所以关于j的遍历顺序是正序的。

# include<iostream>
# include<vector>using namespace std;int main(){int n, w;cin >> n >> w;vector<int> weights(n);vector<int> values(n);for(int i=0; i<n; ++i)cin >> weights[i] >> values[i];// dp数组 dp[i][j]表示从下标为[0-i]的物品,每个物品可以取无限次// 放进容量为j的背包,价值总和最大是多少vector<int> dp(w+1);// 循环  dp方程for(int i=0; i<n; ++i)for(int j=weights[i]; j<=w; ++j)dp[j] = max(dp[j], dp[j-weights[i]] + values[i]);cout << dp[w] << endl;return 0;
}

2、零钱兑换Ⅱ 518

这个已知背包容量,且物品数量有无数个,求能够填满背包的方法数。这题与上一篇博客中目标和很相似,都是求填满背包的方法数,但是这里是完全背包,目标和问题是01背包。这里直接套用完全背包的代码框架,需要在dp方程和初始化上稍作修改。

class Solution {
public:int change(int amount, vector<int>& coins) {vector<uint64_t> dp(amount + 1);dp[0] = 1;for(int i=0; i<coins.size(); ++i)for(int j=coins[i]; j<=amount; ++j)dp[j] += dp[j-coins[i]];return dp[amount];}
};

3、组合总和 Ⅳ 377

这题也是已知背包容量,且物品数量有无数个,求能够填满背包的方法的排列数。这题和上一题零钱兑换Ⅱ的区别在于这题是求排列,关注结果的顺序,而上一题是求组合,不关注结果的顺序。
如果求组合数就是外层for循环遍历物品,内层for遍历背包。这样得到的方法是按照物品的顺序进行排列,通过循环人为规定一个顺序。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。这样可以遍历到所有的顺序。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<uint64_t> dp(target + 1);dp[0] = 1;for(int j=1; j<=target; ++j)for(int i=0; i<nums.size(); ++i)if(j >= nums[i])dp[j] += dp[j-nums[i]];return dp[target];}
};

4、爬楼梯 70

这里我们从01背包的视角来重新分析这道dp简单题。以n阶楼顶为背包,每次走1~m步为物品,且物品不限次数,求装满背包有多少种方法,方法内物品在意顺序,这是个排列结果,所以需要先遍历背包,后遍历物品。

# include<iostream>
# include<vector>using namespace std;int main(){int m, n;cin >> n >> m;vector<int> dp(n + 1);dp[0] = 1;for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j)if(i-j >= 0)dp[i] += dp[i-j];cout << dp[n] << endl;return 0;
}

二、写在后面

第一题是完全背包的经典问题,求装满背包的最大价值。
对于第二、三题,需要清楚 遍历顺序,如果求组合数就是外层for循环遍历物品,内层for遍历背包。如果求排列数就是外层for遍历背包,内层for循环遍历物品。
第四题爬楼梯问题其实就是完全背包问题,与第三题组合总和Ⅳ一模一样。

相关文章:

【Day32 LeetCode】动态规划DP Ⅴ 完全背包

一、动态规划DP Ⅴ 完全背包 1、完全背包理论 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品都有无限个&#xff08;也就是可以放入背包多次&#xff09;&#xff0c;求解将哪些物品装入背包里物品价值总和…...

景区如何打造高质量游览观光车,提高人流量?

景区如何打造高质量游览观光车&#xff0c;提高人流量&#xff1f; 在旅游业蓬勃发展的今天&#xff0c;各大景区迎来了前所未有的游客热潮。尤其是在春节、五一、国庆等节假日期间&#xff0c;游客数量更是激增。作为景区交通的重要组成部分&#xff0c;游览观光车不仅承载着…...

【Ubuntu】ARM交叉编译开发环境解决“没有那个文件或目录”问题

【Ubuntu】ARM交叉编译开发环境解决“没有那个文件或目录”问题 零、起因 最近在使用Ubuntu虚拟机编译ARM程序&#xff0c;解压ARM的GCC后想要启动&#xff0c;报“没有那个文件或目录”&#xff0c;但是文件确实存在&#xff0c;环境配置也检查过了没问题&#xff0c;本文记…...

蓝桥杯之c++入门(六)【string(practice)】

目录 练习1&#xff1a;标题统计方法1&#xff1a;一次性读取整行字符&#xff0c;然后统计方法2&#xff1a;按照单词读取小提示&#xff1a; 练习2&#xff1a;石头剪子布练习3&#xff1a;密码翻译练习4&#xff1a;文字处理软件练习5&#xff1a;单词的长度练习6&#xff1…...

go的sync包学习

包含了sync.Mutex,sync.RWMutex,sync.Cond,sync.Map,sync.Once等demo sync.Mutex //讲解mutex import ("fmt""math/rand""sync""time" )type Toilet struct {m sync.Mutex } type Person struct {Name string }var DateTime "2…...

互联网上常见的,ip地址泛播什么意思

互联网上常见的&#xff0c;ip地址泛播什么意思&#xff01; 泛播通过将IP地址广播发送到网络中的所有设备&#xff0c;使得这些设备能够接收到相关信息。例如&#xff0c;DHCP服务器在局域网中广播提供IP地址的请求&#xff0c;以便新设备能够获取一个可用的IP地址。此外&…...

Linux/C高级(精讲)----shell结构语句、shell数组

shell脚本 功能性语句 test 可测试对象三种&#xff1a;字符串 整数 文件属性 每种测试对象都有若干测试操作符 1&#xff09;字符串的测试&#xff1a; s1 s2 测试两个字符串的内容是否完全一样 s1 ! s2 测试两个字符串的内容是否有差异 -z s1 测试s1 字符串的长度是…...

14.kafka开机自启动配置

要在Linux(RHEL7.7)系统中设置kafka开机自启动&#xff0c;可以创建一个系统服务单元文件。以下是为详细配置部署&#xff0c;假设你已经安装了kafka并且可以通过kafka-server-start.sh命令启动它。 1.进入/lib/systemd/system目录 命令&#xff1a; cd /lib/systemd/system…...

11 享元(Flyweight)模式

享元模式 1.1 分类 &#xff08;对象&#xff09;结构型 1.2 提出问题 做一个车管所系统&#xff0c;将会产生大量的车辆实体&#xff0c;如果每一个实例都保存自己的所有信息&#xff0c;将会需要大量内存&#xff0c;甚至导致程序崩溃。 1.3 解决方案 运用共享技术有效…...

PHP JSON操作指南

PHP JSON操作指南 概述 JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;易于人阅读和编写&#xff0c;同时也易于机器解析和生成。PHP作为一门流行的服务器端脚本语言&#xff0c;支持对JSON数据进行读取、编写和解析。本文将…...

【学习笔记】计算机图形学的几何数学基础知识

3D坐标系 左手系和右手系 点 x,y,z与w(齐次坐标) 矩阵 第一个下标表示行号,第二个下标表示列号。矩阵乘法不满足交换律矩阵乘法=矩阵合并一个矩阵乘以它的逆矩阵=单位矩阵变化矩阵 平移矩阵 缩放矩阵 除了可以缩放, 还可以利用缩放,在给定右手系的情况确定左手系…...

Python因为网络原因安装依赖库报错

现象 在终端运行以下指令 pip install pyautogui pillow keyboard 出现报错&#xff0c;终端信息如下&#xff1a; PS D:\code\Python> pip install pyautogui pillow keyboard Collecting pyautoguiUsing cached PyAutoGUI-0.9.54.tar.gz (61 kB)Installing build depe…...

什么是卸荷器?风力发电为什么要用卸荷器

目前市场上&#xff0c;那些功率低于400W的小型风力发电机&#xff0c;普遍缺乏刹车、稳速或限速机制。只要有足够的风力&#xff0c;发电机便会开始转动并产生电力。风力越强&#xff0c;转速就越快&#xff0c;这可能导致发电机因转速过高而损坏&#xff0c;甚至发生风机头飞…...

SQL Server详细使用教程(包含启动SQL server服务、建立数据库、建表的详细操作) 非常适合初学者

SQL Server详细使用教程(包含启动SQL server服务、建立数据库、建表的详细操作) 非常适合初学者 文章目录 目录 前言 一、启动SQL server服务的三种方法 1.不启动SQL server服务的影响 2.方法一&#xff1a;利用cmd启动SQL server服务 3.方法二&#xff1a;利用SQL Serv…...

大数据学习之Spark分布式计算框架RDD、内核进阶

一.RDD 28.RDD_为什么需要RDD 29.RDD_定义 30.RDD_五大特性总述 31.RDD_五大特性1 32.RDD_五大特性2 33.RDD_五大特性3 34.RDD_五大特性4 35.RDD_五大特性5 36.RDD_五大特性总结 37.RDD_创建概述 38.RDD_并行化创建 演示代码&#xff1a; // 获取当前 RDD 的分区数 Since ( …...

Unity 加载OSGB(webgl直接加载,无需转换格式!)

Unity webgl加载倾斜摄影数据 前言效果图后续不足 前言 Unity加载倾斜摄影数据&#xff0c;有很多的插件方便好用&#xff0c;但是发布到网页端均失败&#xff0c;因为webgl 的限制&#xff0c;IO读取失效。 前不久发现一个开源项目: UnityOSGB-main 通过两种方式在 Unity 中…...

tcp/ip网络协议,tcp/ip网络协议栈

TCP/IP网络协议和TCP/IP网络协议栈是互联网通信的基石&#xff0c;它们定义了电子设备如何连入因特网以及数据如何在它们之间传输的标准。以下是对TCP/IP网络协议和TCP/IP网络协议栈的详细解释&#xff1a; 一、TCP/IP网络协议 TCP/IP&#xff08;Transmission Control Proto…...

【Debug】the remote host closed the connection错误信息分析

出现的情况说明&#xff1a;QT软件。刚开始都可以连接成功 之后连接 断开几次 就会出现连接失败 错误信息是the remote host closed the connection。the remote host closed the connection广泛原因分析 这个错误通常意味着远端 STM32 服务器主动关闭了连接。可能的原因包括&a…...

SpringBoot扩展篇:@Scope和@Lazy源码解析

SpringBoot扩展篇&#xff1a;Scope和Lazy源码解析 1. 研究主题及Demo2. 注册BeanDefinition3. 初始化属性3.1 解决依赖注入3.2 创建代理 ContextAnnotationAutowireCandidateResolver#getLazyResolutionProxyIfNecessary3.3 代理拦截处理3.4 单例bean与原型bean创建的区别 4. …...

“AI隐患识别系统,安全多了道“智能护盾”

家人们&#xff0c;在生活和工作里&#xff0c;咱们都知道安全那可是头等大事。不管是走在马路上&#xff0c;还是在工厂车间忙碌&#xff0c;又或是住在高楼大厦里&#xff0c;身边都可能藏着一些安全隐患。以前&#xff0c;发现这些隐患大多靠咱们的眼睛和经验&#xff0c;可…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...