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

【动态规划】落花人独立,微雨燕双飞 - 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背包问题之动态规划解法技巧. &#x1f40e;文章专栏: 动态规划 &#x1f680;若有问题 评论区见 ❤ 欢迎大家点赞 评论 收藏 分享 如果你不知道分享给谁,那就分享给薯条. 你们的支持是我不断创作的动力 . 王子,公主请阅&#x1f680; 要开心要快乐顺便…...

浅说树上差分——点差分

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

All in大模型!智能座舱语音交互决胜2025

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

windows git bash 使用zsh 并集成 oh my zsh

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

Git进阶笔记系列(01)Git核心架构原理 | 常用命令实战集合

读书笔记&#xff1a;卓越强迫症强大恐惧症&#xff0c;在亲子家庭、职场关系里尤其是纵向关系模型里&#xff0c;这两种状态很容易无缝衔接。尤其父母对子女、领导对下属&#xff0c;都有望子成龙、强将无弱兵的期望&#xff0c;然而在你的面前&#xff0c;他们才是永远强大的…...

IDEA导入Maven工程不识别pom.xml

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

AT8870单通道直流电机驱动芯片

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

计算机视觉算法实战——实体物体跟踪

✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ ​ ​​​​​​​ ​ 1. 领域介绍✨✨ 实体物体跟踪&#xff08;Object Tracking&#xff09;是计算机视觉领域中的一个重要研究方向&#x…...

网络协议如何确保数据的安全传输?

网络协议作为计算机网络通信的基石&#xff0c;其设计不仅旨在实现数据的有效传输&#xff0c;更在于确保数据在传输过程中的安全性。对于网络协议如何保障数据安全传输&#xff0c;是很多企业和网络IT部门的重点&#xff0c;本文将从多方面概述相关方法。 加密与解密机制 1. …...

在elasticsearch中,document数据的写入流程如何?

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

【优选算法】6----查找总价格为目标值的两个商品

这道题相对于前寄到算法题较为容易~ 同样也是使用了双指针的算法哦~ ----------------------------------------begin-------------------------------------- 题目解析&#xff1a; 题目也是很简单地一句话&#xff0c;但是意图还是很明确~ 讲解算法原理&#xff1a; 同样的&…...

99.8 金融难点通俗解释:净资产收益率(ROE)

目录 0. 承前1. 简述2. 比喻&#xff1a;养母鸡赚钱2.1 第一步&#xff1a;投资母鸡2.2 第二步&#xff1a;母鸡下蛋2.3 第三步&#xff1a;计算赚钱2.4 第四步&#xff1a;计算ROE 3. 生活中的例子3.1 好的ROE3.2 一般的ROE3.3 差的ROE 4. 小朋友要注意4.1 ROE高不一定好4.2 R…...

Java设计模式—观察者模式

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

人工智能在数字化转型中的角色:从数据分析到智能决策

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

论文阅读 Multi-view Classification Using Hybrid Fusion and Mutual Distillation

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

AIGC浪潮下,图文内容社区数据指标体系如何构建?

文章目录 01 案例&#xff1a;以图文内容社区为例实践数据指标体构建02 4个步骤实现数据指标体系构建1. 明确业务目标&#xff0c;梳理北极星指标2. 梳理业务流程&#xff0c;明确过程指标3. 指标下钻分级&#xff0c;构建多层级数据指标体系4. 添加分析维度&#xff0c;构建完…...

”彩色的验证码,使用pytesseract识别出来的验证码内容一直是空“的解决办法

问题&#xff1a;彩色的验证码&#xff0c;使用pytesseract识别出来的验证码内容一直是空字符串 原因&#xff1a;pytesseract只识别黑色部分的内容 解决办法&#xff1a;先把彩色图片精确转换成黑白图片。再将黑白图片进行反相&#xff0c;将验证码部分的内容变成黑色&#…...

前端Vue2项目使用md编辑器

项目中有一个需求&#xff0c;要在前端给用户展示内容&#xff0c;内容有 AI 生成的&#xff0c;返回来的是 md 格式&#xff0c;所以需要给用户展示 md 格式&#xff0c;并且管理端也可以编辑这个 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…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...