【动态规划】落花人独立,微雨燕双飞 - 8. 01背包问题
本篇博客给大家带来的是01背包问题之动态规划解法技巧.
🐎文章专栏: 动态规划
🚀若有问题 评论区见
❤ 欢迎大家点赞 评论 收藏 分享
如果你不知道分享给谁,那就分享给薯条.
你们的支持是我不断创作的动力 .
王子,公主请阅🚀
- 要开心
- 要快乐
- 顺便进步
- 1. 01背包
- 2. 分割等和子集
要开心
要快乐
顺便进步
1. 01背包
题目链接: DP41 【模板】01背包
题目内容:
描述
示例1
输入:
3 5
2 10
4 5
1 4
输出:
14
9
说明:
装第一个和第三个物品时总价值最大,但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。
示例2
输入:
3 8
12 6
11 8
6 8
输出:
8
0
说明:
装第三个物品时总价值最大但是不满,装满背包无解。
备注:
要求O(nV)的时间复杂度,O(V)空间复杂度
第一Ⅰ问的动态规划
1. 状态表示
01背包问题本质上还是 线性dp问题,按线性dp来定义状态即可.
第Ⅰ问: 尝试一维定义
dp[i] 表示在前 i 个位置中选择物品, 在所有的选法中, 物品总体积不超过背包容量V 时的最大价值.
上述一维定义在写状态转移方程时不能保证所选物品体积不会超过背包的容量,并且选完之后背包剩余容量也时未知的.一维定义解决不了问题,
用二维定义dp[i][j] 表示在前 i 个位置中选择物品, 物品总体积不超过 V的所有选法中能选出来的最大价值.
2. 状态转移方程
根据最后一个位置是否选择, 来划分问题:
① i 物品不选, dp[i] = dp[i-1][j]
② i 物品要选, 需要保证剩余容量大于等于0, j-v[i]>= 0, w[i] + dp[i-1][j-v[i]];
3. 初始化
选择物品是从下标1 开始的, 到n结束, 那么dp表就需要多创建一行一列,处理两个细节问题:
①下标之间的对应关系: i -> i j -> j
②初始化虚拟节点:
第一行表示的是 物品可选,总体积不超过 j 的最大价值. 既然没有物品,那就不选,全都为0.
第一列表示的是 所选物品总体积不超过0的最大价值. 此时最大价值就是0,不选即可,全都为0.
4. 填表顺序
根据状态转移方程可知,要想得到dp[i][j] 就得先知道dp[i-1][j]或者dp[i-1][j-v[i]],
所以应该从上往下填写每一行
从左往右填写每一列.
5. 返回值
打印 dp[n][V]即可.
第二 Ⅱ问的动态规划
1. 状态表示
与第Ⅰ问同样的分析方法:
二维定义dp[i][j] 表示在前 i 个位置中选择物品, 物品总体积刚好为 V的所有选法中能选出来的最大价值.
可能存在所有选法都不能恰好装满背包,我们规定此时dp[i][j] = -1;
2. 状态转移方程
根据最后一个位置是否选择, 来划分问题:
① i 物品不选, dp[i] = dp[i-1][j]
② i 物品要选, 需要保证剩余容量大于等于0, j-v[i]>= 0, w[i] + dp[i-1][j-v[i]];
3. 初始化
选择物品是从下标1 开始的, 到n结束, 那么dp表就需要多创建一行一列,处理两个细节问题:
①下标之间的对应关系: i -> i j -> j
②初始化虚拟节点:
第一行表示的是 没有物品可选,总体积等于 j 的最大价值.dp[0][0] = 0, 后面 无论选不选,总价值都达不到 j ,于是全都初始化为-1.
第一列表示的是 所选物品总体积等于0的最大价值. 此时最大价值就是0,不选即可,全都为0.
4. 填表顺序
根据状态转移方程可知,要想得到dp[i][j] 就得先知道dp[i-1][j]或者dp[i-1][j-v[i]],
所以应该从上往下填写每一行
从左往右填写每一列.
5. 返回值
打印 dp[n][V]即可.
第三 优化
①利用滚动数组做空间上的优化
②直接在原始代码上修改
Ⅰ删除所有的 i 维
(★)Ⅱ 填表时从右往左遍历 j .
第四 代码实现
// //优化前:// Scanner in = new Scanner(System.in);// int N = 1010;// // 注意 hasNext 和 hasNextLine 的区别// int n = in.nextInt();// int V = in.nextInt();// int[][] dp1 = new int[N][N];// int[][] dp2 = new int[N][N];// int[] v = new int[N];// int[] w = new int[N];// for (int i = 1; i <= n; ++i) {// v[i] = in.nextInt();// w[i] = in.nextInt();// }// //1.解决第一个问题(1)求这个背包至多能装多大价值的物品?// //填表// for (int i = 1; i <= n; ++i) {// for (int j = 0; j <= V; ++j) { //修改遍历顺序// dp1[i][j] = dp1[i-1][j];// if(j >= v[i]) {// dp1[i][j] = Math.max(dp1[i][j], w[i] + dp1[i-1][j - v[i]]);// }// }// }// System.out.println(dp1[n][V]);// //2. 解决第二个问题 (2)若背包恰好装满,求至多能装多大价值的物品?// for (int i = 1; i <= V; ++i) {// dp2[0][i] = -1;// }// for (int i = 1; i <= n; ++i) {// for (int j = 0; j <= V; ++j) {// dp2[i][j] = dp2[i-1][j];// if (j-v[i] >= 0 && dp2[i-1][j - v[i]] != -1) {// dp2[i][j] = Math.max(dp2[i][j], w[i] + dp2[i-1][j - v[i]]);// }// }// }// //若是-1则输出0, 若不是则正常输出.// System.out.println((dp2[n][V] == -1 ? 0 : dp2[n][V]));//优化后:Scanner in = new Scanner(System.in);int N = 1010;// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();int V = in.nextInt();int[] dp1 = new int[N];int[] dp2 = new int[N];int[] v = new int[N];int[] w = new int[N];for (int i = 1; i <= n; ++i) {v[i] = in.nextInt();w[i] = in.nextInt();}//1.解决第一个问题(1)求这个背包至多能装多大价值的物品?//填表for (int i = 1; i <= n; ++i) {for (int j = V; j >= v[i]; --j) { //修改遍历顺序dp1[j] = Math.max(dp1[j], w[i] + dp1[j - v[i]]);}}System.out.println(dp1[V]);//2. 解决第二个问题 (2)若背包恰好装满,求至多能装多大价值的物品?for (int i = 1; i <= V; ++i) {dp2[i] = -1;}for (int i = 1; i <= n; ++i) {for (int j = V; j >= v[i]; --j) {if (dp2[j - v[i]] != -1) {dp2[j] = Math.max(dp2[j], w[i] + dp2[j - v[i]]);}}}//若是-1则输出0, 若不是则正常输出.System.out.println((dp2[V] == -1 ? 0 : dp2[V]));
2. 分割等和子集
题目链接: 416. 分割等和子集
题目内容:
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
第一 预处理
直接去判断两个子集的元素和是否相等会有点复杂, 可以转化为只研究一个子集等于原数组元素和的一半, 即在数组中选择一些数, 这些数的和是否等于原数组元素和的一半.
第二 动态规划
1. 状态表示
根据第一题模板题可知定义状态的方式:
dp[i][j]表示在nums的前 i 个位置中选择一些数,所有选法中,是否存在一些数,使得这些数之和为 j.
2. 状态转移方程
根据最后一个位置nums[i]是否选择来划分情况:
①nums[i]不选: dp[i][j] = dp[i-1][j];
②nums[i]要选: 需要保证所选数之和不超过 j . j - nums[i] >= 0, dp[i][j-nums[i]];
3. 初始化
dp表多创建一行一列,需要处理两个问题:
①dp表与nums表元素之间的对应关系:
i -> i-1; j -> j-1
②初始化虚拟节点(就是多创建的一行一列),保证填表的正确性:
第一行 i=0意味着没有元素可选,怎么选最大值都只能是0,所以dp[0][0] = true,其余全部初始化为false.
第一列 j=0意味着需要凑成和为0, 直接不选即可. 故从i=1开始全部初始化为true.
4. 填表顺序
根据状态转移方程可知,要想求得dp[i][j]就得先知道dp[i-1][j]和dp[i-1][j-nums[i]],所以可知填表顺序为:
从上往下填写每一行
每一行从左往右填写
5. 返回值
返回dp[nums.length][原数组元素和的一半]
第三 优化
①利用滚动数组做空间上的优化
②直接在原始代码上修改
Ⅰ删除所有的 i 维
(★)Ⅱ 填表时从右往左遍历 j .
第四 代码实现
class Solution {public boolean canPartition(int[] nums) {// int n = nums.length;// int sum = 0;// for(int x : nums) sum += x;// if(sum%2 == 1) return false;// int aim = sum/2;// boolean[][] dp = new boolean[n+1][aim+1];// for(int i = 0;i <= n;++i) {// dp[i][0] = true;// }// for(int i = 1;i <= n;++i) {// if(i < n) {// sum += nums[i];// }// for(int j = 1;j <= aim;++j) {// dp[i][j] = dp[i-1][j];// if(j >= nums[i-1] && dp[i][j] == false) {// dp[i][j] = dp[i-1][j-nums[i-1]];// }// }// }// return dp[n][aim];// }//优化: 删除第一维, 从右往左遍历第二维int n = nums.length;int sum = 0;for(int x : nums) sum += x;if(sum%2 == 1) return false;int aim = sum/2;boolean[] dp = new boolean[aim+1];dp[0] = true;for(int i = 1;i <= n;++i) {if(i < n) {sum += nums[i];}for(int j = aim;j >= nums[i-1];--j) { //修改遍历顺序,本质上是滚动数组的优化.if(dp[j] == false) {dp[j] = dp[j-nums[i-1]];}}}return dp[aim];}
}
本篇博客到这里就结束啦, 感谢观看 ❤❤❤
🐎期待与你的下一次相遇😊😊😊
相关文章:

【动态规划】落花人独立,微雨燕双飞 - 8. 01背包问题
本篇博客给大家带来的是01背包问题之动态规划解法技巧. 🐎文章专栏: 动态规划 🚀若有问题 评论区见 ❤ 欢迎大家点赞 评论 收藏 分享 如果你不知道分享给谁,那就分享给薯条. 你们的支持是我不断创作的动力 . 王子,公主请阅🚀 要开心要快乐顺便…...

浅说树上差分——点差分
我们前面也学过差分,现在的话我们就把他放到树上来做。因为这是树,所以会有点和边之分,所以树上差分也会分为 点差分 和 边差分 。 引入 树上差分其实和线性差分没有什么区别,只不过是放到了树上的两点,而他们之间的…...

All in大模型!智能座舱语音交互决胜2025
大模型加速上车,AI智能座舱竞争更显白热化。 诚然,在语言大模型为核心的多模态能力加持下,智能语音助理能够理解复杂的语言指令,实现知识问答、文本生成等,以及根据上下文进行逻辑推理,提供更智能、准确的…...

windows git bash 使用zsh 并集成 oh my zsh
参考了 这篇文章 进行配置,记录了自己的踩坑过程,并增加了 zsh-autosuggestions 插件的集成。 主要步骤: 1. git bash 这个就不说了,自己去网上下,windows 使用git时候 命令行基本都有它。 主要也是用它不方便&…...

Git进阶笔记系列(01)Git核心架构原理 | 常用命令实战集合
读书笔记:卓越强迫症强大恐惧症,在亲子家庭、职场关系里尤其是纵向关系模型里,这两种状态很容易无缝衔接。尤其父母对子女、领导对下属,都有望子成龙、强将无弱兵的期望,然而在你的面前,他们才是永远强大的…...

IDEA导入Maven工程不识别pom.xml
0 现象 把阿里 sentinel 项目下载本地后,IDEA 中却没显示 maven 工具栏。 1 右键Maven Projects 点击IDEA右侧边栏的Maven Projects,再点击: 在出现的选择框中选择指定的未被识别的pom.xml即可: 2 Add as maven project 右键p…...

AT8870单通道直流电机驱动芯片
AT8870单通道直流电机驱动芯片 典型应用原理图 描述 AT8870是一款刷式直流电机驱动器,适用于打印机、电器、工业设备以及其他小型机器。两个逻辑输入控制H桥驱动器,该驱动器由四个N-MOS组成,能够以高达3.6A的峰值电流双向控制电机。利用电流…...

计算机视觉算法实战——实体物体跟踪
✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ 1. 领域介绍✨✨ 实体物体跟踪(Object Tracking)是计算机视觉领域中的一个重要研究方向&#x…...
网络协议如何确保数据的安全传输?
网络协议作为计算机网络通信的基石,其设计不仅旨在实现数据的有效传输,更在于确保数据在传输过程中的安全性。对于网络协议如何保障数据安全传输,是很多企业和网络IT部门的重点,本文将从多方面概述相关方法。 加密与解密机制 1. …...

在elasticsearch中,document数据的写入流程如何?
本文将为您介绍文档内容是如何写入ES集群中。 数据写入ES集群的流程图如下 流程介绍 用户携带数据发起POST请求指向集群9200端口。9200端口将数据写入请求发给主分片。主分片会对数据进行分片计算分发给具体分片。(计算方式:hash % primary_number_sha…...

【优选算法】6----查找总价格为目标值的两个商品
这道题相对于前寄到算法题较为容易~ 同样也是使用了双指针的算法哦~ ----------------------------------------begin-------------------------------------- 题目解析: 题目也是很简单地一句话,但是意图还是很明确~ 讲解算法原理: 同样的&…...
99.8 金融难点通俗解释:净资产收益率(ROE)
目录 0. 承前1. 简述2. 比喻:养母鸡赚钱2.1 第一步:投资母鸡2.2 第二步:母鸡下蛋2.3 第三步:计算赚钱2.4 第四步:计算ROE 3. 生活中的例子3.1 好的ROE3.2 一般的ROE3.3 差的ROE 4. 小朋友要注意4.1 ROE高不一定好4.2 R…...

Java设计模式—观察者模式
观察者模式 目录 观察者模式1、什么是观察者模式?2、观察者模式优缺点及注意事项?3、观察者模式实现?4、手写线程安全的观察者模式? 1、什么是观察者模式? - 实例:现实生活中很多事物都是依赖存在的&#x…...

人工智能在数字化转型中的角色:从数据分析到智能决策
引言 在数字化转型浪潮中,人工智能(AI)正迅速崛起,成为推动企业创新和变革的关键力量。面对日益复杂的市场环境和激烈的行业竞争,企业亟需借助技术手段提高运营效率、优化决策过程,并增强市场竞争力。而AI…...

论文阅读 Multi-view Classification Using Hybrid Fusion and Mutual Distillation
Multi-view Classification Using Hybrid Fusion and Mutual Distillation Intro 多视角问题可以分为两类: Structured。固定视角,或预先定义的视角的问题。unstructured。 本文的三大contributions: 引入了混合的多视角融合策略。使用了…...

AIGC浪潮下,图文内容社区数据指标体系如何构建?
文章目录 01 案例:以图文内容社区为例实践数据指标体构建02 4个步骤实现数据指标体系构建1. 明确业务目标,梳理北极星指标2. 梳理业务流程,明确过程指标3. 指标下钻分级,构建多层级数据指标体系4. 添加分析维度,构建完…...
”彩色的验证码,使用pytesseract识别出来的验证码内容一直是空“的解决办法
问题:彩色的验证码,使用pytesseract识别出来的验证码内容一直是空字符串 原因:pytesseract只识别黑色部分的内容 解决办法:先把彩色图片精确转换成黑白图片。再将黑白图片进行反相,将验证码部分的内容变成黑色&#…...

前端Vue2项目使用md编辑器
项目中有一个需求,要在前端给用户展示内容,内容有 AI 生成的,返回来的是 md 格式,所以需要给用户展示 md 格式,并且管理端也可以编辑这个 md 格式的文档。 使用组件库 v-md-editor。 https://code-farmer-i.github.i…...
OpenVela 架构剖析:从内核到应用
目录 一、总体架构概述 二、 内核层 2.1. OpenVela架构的内核基础 2.2. 内核层的主要职责 2.3. OpenVela对NuttX的扩展与优化 三、系统服务层 2.1. 进程管理 2.2. 内存管理 2.3. 文件系统 2.4. 网络通信 四、框架层 4.1. 模块化设计 4.2. API接口 4.3. 组件和服务…...

vue视频流播放,支持多种视频格式,如rmvb、mkv
先将视频转码为ts ffmpeg -i C:\test\3.rmvb -codec: copy -start_number 0 -hls_time 10 -hls_list_size 0 -f hls C:\test\a\output.m3u8 后端配置接口 import org.springframework.core.io.Resource; import org.springframework.core.io.UrlResource; import org.spring…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...