代码随想录算法训练营第三十四天 | 01背包问题 416.分割等和子集

01背包问题—1(dp为二维数组):

文章链接
题目链接:卡码网 46

思路:

因为有物品和背包容量两个方面,因此我们使用二维数组保存递推的结果

  • ① dp数组及下标的含义:
    dp[i][j],其中 i 是第 i 个物品,j是背包容量,dp[i][j]表示在背包容量为 j 时,在[0, i]物品中任取所能取得的最大价值
  • ② 递推公式:
    根据是否取物品 i 来确定递推公式:
    1)如果不取物品 i ,那么dp[i][j] = dp[i - 1][j]
    2)如果取物品 i,那么背包容量剩余 j - weight[i],在[0, i - 1]物品中任取所能取得的最大价值为dp[i - 1][j - weight[i]]。因此dp[i][j] = dp[i - 1][j - weight[i]] + value[i]
    因此dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
    当背包容量 j 能放下物品 i 时
  • ③ 初始化:
    物品 i 的范围为[0, M - 1],背包容量 j 的范围为[0, N]
    因此设定的dp为M×(N + 1)的数组
dp = [[0] * (N + 1) for _ in range(M)]

初始化第0列为全0,因为背包容量为0时放不了任何东西
由递推公式可知,还需要初始化第0行,那么就是,如果背包容量不能放下第0物品,dp为0;否则为value[0]

for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]
  • ④ 遍历方式
    由于dp递推式中dp[i][j]需要的信息都在其左上方,因此只要是先遍历完左上方的都可以。
    比如先遍历物品再遍历容量,或者先遍历容量再遍历物品。其中先物品后容量是比较好理解的
  • ⑤ 举例:
    背包重量 4,物品的重量及价值
    在这里插入图片描述
    推导的dp数组
    在这里插入图片描述

感悟:

dp数组及下标的含义,初始化以及遍历时记得下标的含义从而得到正确的范围


01背包问题–2(dp为一维数组):

文章链接
题目链接:卡码网 46
二维dp数组的01背包递推式为:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]),其中 i 为物品下标, j 为背包容量,dp[i][j]为从下标为[0, i]的物品里任意取,放进容量为 j 的背包,价值总和最大是多少
那么如果将第 i - 1行的内容复制到第 i 行,那么递推公式为
dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])
那么实际上就可以按行状态压缩为一维数组dp(将原来二维的压缩为了原来的一行)
递推式为dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

  • ① dp数组及下标的含义
    dp[j]表示背包容量为 j 能放进的最大价值
  • ② 递推式
    递推式为dp[j] = max(dp[j], dp[j - weight[i]] + value[i])(如果背包能放进下标为 i 的物品)
  • ③ 初始化
    dp[0] = 0,背包容量为0放不了物品, j ≠ 0 如何初始化呢。查看递推式
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]),每次取最大值,如果题目给的价值都是正整数,那么dp[j]初始化为0
  • ④ 遍历顺序
    1)倒序遍历背包容量:原因,由递推式可知, dp[j] = max(dp[j], dp[j - weight[i]] + value[i]),如果顺序遍历的话,同一个物品会被多次放进背包。如(还是拿上一次举例的物品和背包容量);
    或者也可以这么理解,一维dp数组是由二维dp数组压缩而来,二维的递推式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]),那么一维递推式中的dp[j - weight[i]] + value[i]对应dp[i - 1][j - weight[i]] + value[i],也就是一维数组中dp[x](x =j - weight[i])应当为上一行的值,如果顺序遍历的话,那么dp[x]就是这一行的值,所以要逆序遍历让dp[x]仍然为上一行的值
    为什么二维dp数组遍历时不用倒序,因为dp[i][j]由上一层即dp[i - 1][j]计算而来,遍历本层dp[i][j]时不会覆盖上一层的数据,或者说本层dp[i][j]不会被覆盖
    在这里插入图片描述
    2)只能先遍历物品再遍历背包容量:
    因为遍历背包容量为逆序遍历,所以如果先遍历物品再遍历背包容量的话,那么每次比较的就是空背包中放入一个物品后的价值比较。也就是背包中只能放一个物品了。
    需要注意的是: 因为dp初始化为0,因此遍历物品从0开始;内层循环逆序遍历背包容量只到weight[i]即可。
  • ⑤ 举例
    背包容量为4,物品的重量及价值如下
    在这里插入图片描述
    那么递推的dp为
    在这里插入图片描述
class Solution():def bagSolution(self):material, bagweight = [int(x) for x in input().split()]weight = [int(x) for x in input().split()]value = [int(x) for x in input().split()]dp = [0] * (bagweight + 1)  # 初始化为全0# 先遍历物品,后遍历背包容量for i in range(material):   # 因为初始化为全0,所以第一个物品也要遍历# 内层循环从bagweight空间逐渐减少到当前材料所占空间for j in range(bagweight, weight[i] - 1, -1):  # 倒序dp[j] = max(dp[j], dp[j - weight[i]] + value[i])# 输出dp[bagweight],即在给定N 背包空间可以携带的研究材料的最大价值return dp[-1]solution = Solution()
print(solution.bagSolution())

感悟:

状态压缩二维数组为一维数组,该一维数组是原二维数组的某一行。因为计算dp需要用到其左上角的数据,如果遍历背包容量时顺序遍历,那么左上角数据就会被覆盖,因此需要逆序遍历,且只能先遍历物品,后遍历背包


LeetCode 416.分割等和子集:

文章链接
题目链接:416.分割等和子集

思路:

  1. 将问题修改为适合01背包的解法(dp是求最大值)
    首先本题的目标为在集合中能否找到总和为sum / 2的子集
    可以使用回溯,但是需要剪枝让其不超时。本题我们使用背包问题求解。
    背包问题常见有:01背包、完全背包、多重背包以及分组背包
    如果一个物品可以重复放入背包,那么是完全背包问题;只能放入一次是01背包问题。本题中集合中的元素只能放入一次,因此是01背包问题。
    怎么确定能将01背包问题套入本题
  • 背包体积为 sum / 2
  • 背包要放入的物品的重量为元素的数值,价值也为元素的数值
  • 如果背包正好装满,说明找到了总和为sum / 2的子集
  • 背包中每个元素都不能重复放入
    动规五部曲
  • ① dp及下标的含义
    01背包中,dp[j]:表示容量为 j 的背包,所装的物品最大价值为dp[j]
    应用到本题中: dp[j]表示背包总容量为 j ,放入物品后,背的最大价值,即最大重量为dp[j]
    那么当dp[target] == target时,背包就正好装满了
  • ② 递推公式
    01背包递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    本题中物品的重量和价值都是nums[i]
    因此递推公式为dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
  • ③ 初始化
    从dp[j]的定义来说,dp[0]初始化为0,因为题目给的的价值都是正整数,因此非0下标都初始化为0。如果题目给的价值有负数,那么非0下标要初始化为负无穷
  • ④ 遍历顺序
    先物品后背包容量,且背包容量逆序遍历
  • ⑤ 举例
    dp[j] <= j(一定成立)
    如果dp[j] == j,那么集合可以被分为子集和相同的两个子集
    输入[1, 5, 11, 5]
    在这里插入图片描述
class Solution:def canPartition(self, nums: List[int]) -> bool:if len(nums) == 1:return False_sum = sum(nums)if _sum % 2 == 1:   # 集合和为奇数return Falsetarget = _sum // 2dp = [0] * (target + 1)# 先物品后背包重量for num in nums:# 背包重量逆序遍历for j in range(target, num - 1, -1):dp[j] = max(dp[j], dp[j - num] + num)return dp[-1] == target
  1. 01背包更进一步修改贴合本题(dp值为True or False)
    因为题目要求的是能否将数组分为和相等的两个集合,那么实际上dp数组的值可以为True or False。
    动规五部曲
  • ① dp及下标的含义
    dp[j] : 表示背包容量为 j 能否从集合中找到元素刚好填满背包,能否为dp[j]
  • ② 递推
    考虑是否要将物品 i(即元素 i)加入背包中
    1)如果不加入:dp[j] = dp[j]
    2)如果加入:dp[j] = d[j - nums[i]]
    因此dp[j] = dp[j] or dp[j - nums[i]](因为只要有一个成立就可以了)
  • ③ 初始化
    dp[0] = True(背包为空,相当于可以从集合中找到元素刚好填满背包,即一个都不放),由递推公式dp[j] = dp[j] or dp[j - nums[i]]得,下标非0应当初始化为False(False or x = x,这样让dp数组在遍历时求两个的or,而不是被初始值覆盖)
  • ④ 遍历顺序
    即一维01背包遍历顺序。先物品后背包,背包容量逆序遍历
  • ⑤ 举例
    在这里插入图片描述
"""
思路里面的一维dp数组
使用的是0和1,代表False和True
"""
class Solution:def canPartition(self, nums: List[int]) -> bool:if len(nums) == 1:  # 只有一个元素return FalsesumNums = sum(nums)if sumNums % 2 == 1:    # 集合总和为奇数return False# 动态规划,是否能从集合中挑选出元素满足和为sumNums // 2dp = [0] * (sumNums // 2 + 1)dp[0] = 1   # 初始化# 先遍历集合中的元素for i in range(len(nums)):for j in range(sumNums // 2, nums[i] - 1, -1):dp[j] = (dp[j] or dp[j - nums[i]])if dp[-1] == 1:return Trueelse:return False"""
使用二维dp数组
需要注意的是dp数组的行数为len(nums) + 1,第0行没有物品,为空集。
- dp[i][j]为在集合[1, i]能否找到元素正好填满容量为j的背包,dp[i][j]为能否
- 递推公式为dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
- 初始化:第0列初始化为True(背包为空),那么第0行如何初始化呢
- 如果第0行是物品1能否正好填满容量为j的背包,那么应当dp[0][nums[0]] = True,那么需要考虑到 nums[i] > j的情况。所以不如直接让第0行没有物品,为空集,初始化为False
- 因为第0行没有物品,因此物品从第1行开始,那么nums[i]对应第 i + 1行
"""
class Solution:def canPartition(self, nums: List[int]) -> bool:if len(nums) == 1:return False_sum = sum(nums)if _sum % 2 == 1:return Falsetarget = _sum // 2dp = [[False] * (target + 1) for _ in range(len(nums) + 1)]# 初始化# 第0列应当为True(j = 0),第0行是没有物品,即空集的情况for i in range(len(nums) + 1):dp[i][0] = True# 遍历递推for i in range(1, len(nums) + 1):for j in range(1, target + 1):if j >= nums[i - 1]:	# nums[i - 1]对应第 i 行dp[i][j] = (dp[i - 1][j] or dp[i - 1][j - nums[i - 1]])else:dp[i][j] = dp[i - 1][j]return dp[-1][-1]

感悟:

01背包思路用在其应用题上,需要明确dp、物品重量和价值分别是什么,以及动态规划五部曲


学习收获:

01背包问题的二维dp数组、一维dp数组以及01背包问题的应用

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/462370.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

什么品牌的护眼台灯比较好?五款护眼效果比较明显的护眼台灯

在当今信息爆炸的时代背景下&#xff0c;挑选一款真正符合个人需求的护眼台灯&#xff0c;确实是一项不小的挑战。市场上品牌众多、型号繁杂&#xff0c;功能特点各不相同&#xff0c;价格区间也相当广泛&#xff0c;许多消费者在选购时往往感到迷茫不已。当大家询问“什么品牌…

cv.dnn.blobFromImage参数详解

例如&#xff1a; image cv.imread(imgs/img.png) blob cv.dnn.blobFromImage(image, scalefactor1.0, size(224, 224), mean(0, 0, 0), swapRBTrue, cropFalse) print("原始图像形状:", image.shape) print("Blob数据形状:", blob.shape)1. image 含义…

消息队列-Rabbitmq(消息发送,消息接收)

将来我们开发业务功能的时候&#xff0c;肯定不会在控制台收发消息&#xff0c;而是应该基于编程的方式。由于RabbitMQ采用了AMQP协议&#xff0c;因此它具备跨语言的特性。任何语言只要遵循AMQP协议收发消息&#xff0c;都可以与RabbitMQ交互。并且RabbitMQ官方也提供了各种不…

电脑没有下载声卡驱动怎么办?电脑声卡驱动安装方法

在日常使用电脑的过程中&#xff0c;我们可能会遇到电脑没有声音的问题&#xff0c;这往往与声卡驱动缺失或损坏有关。声卡驱动是连接电脑硬件&#xff08;声卡&#xff09;与操作系统之间的桥梁&#xff0c;确保音频信号能够正常输入输出。那么&#xff0c;当电脑没有声卡驱动…

人工智能与数据安全:Facebook如何应对隐私挑战

在数字时代&#xff0c;数据隐私和安全成为了用户和企业关注的核心问题。作为全球最大的社交媒体平台之一&#xff0c;Facebook面临着日益严峻的隐私挑战。近年来&#xff0c;频繁发生的数据泄露事件和对用户隐私的质疑&#xff0c;使得Facebook在保护用户数据方面倍感压力。为…

使用RabbitMQ实现微服务间的异步消息传递

使用RabbitMQ实现微服务间的异步消息传递 RabbitMQ简介 安装RabbitMQ 在Ubuntu上安装RabbitMQ 在CentOS上安装RabbitMQ 配置RabbitMQ 创建微服务 生产者服务 安装依赖 生产者代码 消费者服务 消费者代码 运行微服务 消息模式 直接模式 生产者代码 消费者代码 扇出模式 生产…

【MySQL】MySQL安装以及各种报错处理

前言&#xff1a; 本节内容讲述在Ubuntu环境下怎么进行MySQL的安装。 以及一些安装过程中遇到的报错如何处理的问题。 ps:注意&#xff0c; 本篇文章不是图形化界面的MySQL安装教程哦。想要安装图形化界面的MySQL的友友们可以另寻资源了。 目录 更新软件包列表 安装M…

Servlet 3.0 注解开发

文章目录 Servlet3.0注解开发修改idea创建注解的servlet模板内容讲解 关于servlet3.0注解开发的疑问_配置路径省略了属性urlPatterns内容讲解内容小结 Servlet3.0注解开发 【1】问题 说明&#xff1a;之前我们都是使用web.xml进行servlet映射路径的配置。这样配置的弊端&…

FPGA时序分析和约束学习笔记(3、Timequest时序路径详解和优化)

FPGA时序分析和约束学习笔记&#xff08;3、Timequest时序路径详解和优化&#xff09; Timequest中Data Path分析 Data Arrival Path clock path&#xff1a;时钟信号到达源寄存器时钟端口的时间 data path&#xff1a;数据从源寄存器Q端口出发到达目标寄存器D端口的时间 D…

windows与windows文件共享

目录 基础设置主机共享文件端设置从机接受文件端设置 基础设置 1、先确保两台电脑直接能够ping通&#xff0c;这是文件共享的前提&#xff0c;如果ping不通就去查找对应的原因&#xff0c;一般都是防火墙的原因。 在ping通的情况下&#xff1a; 2、先找到高级共享设置 3、对专…

前端页面整屏滚动fullpage.js简单使用

官网CSS,JS地址 fullPage.js/dist/fullpage.min.js at master alvarotrigo/fullPage.js GitHub fullPage.js/dist/fullpage.min.css at master alvarotrigo/fullPage.js GitHub <!DOCTYPE html> <html lang"en"><head><meta charset"…

Rust整合Elasticsearch

Elasticsearch是什么 Lucene&#xff1a;Java实现的搜索引擎类库 易扩展高性能仅限Java开发不支持水平扩展 Elasticsearch&#xff1a;基于Lucene开发的分布式搜索和分析引擎 支持分布式、水平扩展提高RestfulAPI&#xff0c;可被任何语言调用 Elastic Stack是什么 ELK&a…

opencv-day2-图像预处理1

图像预处理 在计算机视觉和图像处理领域&#xff0c;图像预处理能够提高后续处理&#xff08;如特征提取、目标检测等&#xff09;的准确性和效率。 常见的图像预处理操作&#xff1a; 图像色彩空间转换 图像大小调整 图像仿射变换 图像翻转 图像裁剪 图像二值化处理 图…

scrapy爬取名人名言

爬取名人名言&#xff1a;http://quotes.toscrape.com/ 1 创建爬虫项目&#xff0c;在终端中输入&#xff1a; scrapy startproject quotes2 创建之后&#xff0c;在spiders文件夹下面创建爬虫文件quotes.py&#xff0c;内容如下&#xff1a; import scrapy from scrapy.spi…

一文了解Linux内核I2C子系统,驱动苹果MFI加密芯片

版本 日期 作者 变更表述 1.0 2024/10/27 于忠军 文档创建 背景&#xff1a;由于苹果有一套MFI IAP2的蓝牙私有协议&#xff0c;这个协议是基于BR/EDR的RFCOMM自定义UUID来实现IAP2协议的通信&#xff0c;中间会牵扯到苹果加密芯片的I2C读取&#xff0c;所以我们借此机…

Spring之依赖注入(DI)和控制反转(IoC)——配置文件、纯注解

依赖注入 依赖注入(Dependency Injection&#xff0c;简称 DI)与控制反转(loC)的含义相同&#xff0c;只不过这两 个称呼是从两个角度描述的同一个概念。对于一个 Spring 初学者来说&#xff0c;这两种称呼很难理解, 下面我们将通过简单的语言来描述这两个概念。 当Java对象&…

Ubuntu 22.04安装部署

一、部署环境 表 1‑1 环境服务版本号系统Ubuntu22.04 server lts运行环境1JDK1.8前端WEBNginx1.8数据库postgresqlpostgresql13postgis3.1pgrouting3.1消息队列rabbitmq3.X(3.0以上)运行环境2erlang23.3.3.1 二、安装系统 2.1安装 1.安装方式&#xff0c;选第一条。 2.选择…

基于ResNet50模型的船型识别与分类系统研究

项目源码获取方式见文章末尾&#xff01; 600多个深度学习项目资料&#xff0c;快来加入社群一起学习吧。 《------往期经典推荐------》 项目名称 1.【LSTM模型实现光伏发电功率的预测】 2.【卫星图像道路检测DeepLabV3Plus模型】 3.【GAN模型实现二次元头像生成】 4.【CNN模…

信息学科平台系统开发:基于Spring Boot的最佳实践

3系统分析 3.1可行性分析 通过对本基于保密信息学科平台系统实行的目的初步调查和分析&#xff0c;提出可行性方案并对其一一进行论证。我们在这里主要从技术可行性、经济可行性、操作可行性等方面进行分析。 3.1.1技术可行性 本基于保密信息学科平台系统采用Spring Boot框架&a…

Cityscapes数据集:如何将像素级的多边形标注的分割数据标注转为目标检测的bbox标注

Cityscapes数据集官网下载地址&#xff1a; https://www.cityscapes-dataset.com/ 相关介绍&#xff1a;从官网下载这三个压缩包文件leftImg8bit_trainvaltest.zip、gtCoarse.zip、gtFine_trainvaltest.zip 1&#xff09;leftImg8bit_trainvaltest.zip分为train、val以及tes…