动态规划练习八(01背包问题)

一、问题介绍与解题心得

01背包问题就是每个物品数量只有一个,每个物品可以取或不取,来达到收益最大,或者收益在某个值。

限制条件:背包容量有限,物品个数只有1个

解决问题:从价值入手(价值最大或是某个值),从容量入手(不超过最大体积还是刚好装到某一个体积)

设的 dp 表一般是 dp[i][j] 表示在 [1, i] 的物品中选择,符合要求 j 的价值

此处以01背包模板题为例:【模板】01背包_牛客题霸_牛客网

1、传统方法

这里根据要求的不同用两个 dp 表解决问题,分析过程不赘述,主要看总结的规律。

由于01背包中物品个数只有一个,所以选不选 i 物品都是去看 dp[i - 1] 位置的值,所以要进行空间优化的话就是用 dp[i - 1][j] 和 dp[i - 1][j - v[i]] 来更新 dp[i] 的值,而我们现在只有一个一维数组,此时要开始更新 dp[i] 那么一维数组中必然存放的是已经更新完成的 dp[i - 1],那已知我们要更新的 dp[i] 是需要旧的一维数组表中的,相对于 j 位置之前的值,所以 dp[i] 的更新一定是从后向前的更新,防止覆盖。

所以总结,01背包问题的空间优化是删去行元素,从后向前更新。

2、空间优化

二、例题

1、分割等和子集

416. 分割等和子集 - 力扣(LeetCode)

2、目标和

494. 目标和 - 力扣(LeetCode)

3、最后一块石头重量2

1049. 最后一块石头的重量 II - 力扣(LeetCode)

三、总结

其实01背包问题就是要你把问题转化成在一段数据里面取出一部分数据满足条件。数据只有一个。

难点就是如何转化成取数据,如第二第三题就是把符号的正负选择转化成在一段数据中取出一些正数来满足题目要求。

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

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

相关文章

Java实习生面试题汇总

Java实习生面试题汇总 简介 本人是二本大三学生,下半年大四。暑假在上海这边找实习工作,面了几家公司,所问到的问题记录在下面。 因为是在校生,没任何实习经历,一般找我面试的都是小公司,一般问的比较简…

开源安全一站式构建!开启企业开源治理新篇章

在如今信息技术日新月异、飞速发展的数字化时代,开源技术如同一股强劲的东风,为企业创新注入了源源不断的活力,然而,正如一枚硬币有正反两面,开源技术的广泛应用亦伴随着不容忽视的挑战。安全风险如影随形,…

xxl-job 自定义告警短信发送

官方介绍 代码实现 实现 JobAlarm 重写 doAlarm 方法 Component public class SmsJobAlarm implements JobAlarm {Overridepublic boolean doAlarm(XxlJobInfo info, XxlJobLog jobLog) {boolean alarmResult true;// 简单内容,根据业务自行修改String template …

大数据学习之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_并行化创建 演示代码: // 获取当前 RDD 的分区数 Since ( …

【分布式架构理论3】分布式调用(2):API 网关分析

文章目录 一、API 网关的作用1. 业务层面:简化调用复杂性2. 系统层面:屏蔽客户端调用差异3. 其他方面: 二、API 网关的技术原理1. 协议转换2. 链式处理3. 异步请求机制1. Zuul1:同步阻塞处理2. Zuul2:异步非阻塞处理 三…

3.【BUUCTF】XSS-Lab1

进入题目页面如下 好好好&#xff0c;提示点击图片&#xff0c;点进去页面如下&#xff0c;且url中有传参&#xff0c;有注入点 发现题目给出了源码 查看得到本题的源码 分析一下代码 <!DOCTYPE html><!--STATUS OK--> <!-- 声明文档类型为 HTML5&#xff0c;告…

uniapp小程序自定义中间凸起样式底部tabbar

我自己写的自定义的tabbar效果图 废话少说咱们直接上代码&#xff0c;一步一步来 第一步&#xff1a; 找到根目录下的 pages.json 文件&#xff0c;在 tabBar 中把 custom 设置为 true&#xff0c;默认值是 false。list 中设置自定义的相关信息&#xff0c; pagePath&#x…

105,【5】buuctf web [BJDCTF2020]Easy MD5

进入靶场 先输入试试回显 输入的值成了password的内容 查看源码&#xff0c;尝试得到信息 什么也没得到 抓包&#xff0c;看看请求与响应里有什么信息 响应里得到信息 hint: select * from admin where passwordmd5($pass,true) 此时需要绕过MD5&#xff08;&#xff09;函…

JVM监控和管理工具

基础故障处理工具 jps jps(JVM Process Status Tool)&#xff1a;Java虚拟机进程状态工具 功能 1&#xff1a;列出正在运行的虚拟机进程 2&#xff1a;显示虚拟机执行主类(main()方法所在的类) 3&#xff1a;显示进程ID(PID&#xff0c;Process Identifier) 命令格式 jps […

【大模型】AI 辅助编程操作实战使用详解

目录 一、前言 二、AI 编程介绍 2.1 AI 编程是什么 2.1.1 为什么需要AI辅助编程 2.2 AI 编程主要特点 2.3 AI编程底层核心技术 2.4 AI 编程核心应用场景 三、AI 代码辅助编程解决方案 3.1 AI 大模型平台 3.1.1 AI大模型平台代码生成优缺点 3.2 AI 编码插件 3.3 AI 编…

机器学习--2.多元线性回归

多元线性回归 1、基本概念 1.1、连续值 1.2、离散值 1.3、简单线性回归 1.4、最优解 1.5、多元线性回归 2、正规方程 2.1、最小二乘法 2.2、多元一次方程举例 2.3、矩阵转置公式与求导公式 2.4、推导正规方程0的解 2.5、凸函数判定 成年人最大的自律就是&#xff1a…

2025最新软件测试面试大全(附答案+文档)

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 1、问&#xff1a;你在测试中发现了一个bug&#xff0c;但是开发经理认为这不是一个bug&#xff0c;你应该怎样解决? 首先&#xff0c;将问题提交到缺陷管理库里…

手写MVVM框架-环境搭建

项目使用 webpack 进行进行构建&#xff0c;初始化步骤如下: 1.创建npm项目执行npm init 一直下一步就行 2.安装webpack、webpack-cli、webpack-dev-server&#xff0c;html-webpack-plugin npm i -D webpack webpack-cli webpack-dev-server html-webpack-plugin 3.配置webpac…

如何自定义软件安装路径及Scoop包管理器使用全攻略

如何自定义软件安装路径及Scoop包管理器使用全攻略 一、为什么无法通过WingetUI自定义安装路径&#xff1f; 问题背景&#xff1a; WingetUI是Windows包管理器Winget的图形化工具&#xff0c;但无法直接修改软件的默认安装路径。原因如下&#xff1a; Winget设计限制&#xf…

数据结构实战之线性表(三)

目录 1.顺序表释放 2.顺序表增加空间 3.合并顺序表 4.线性表之链表实现 1.项目结构以及初始代码 2.初始化链表(不带头结点) 3.链表尾部插入数据并显示 4.链表头部插入数据 5.初始化链表&#xff08;带头结点&#xff09; 6.带头结点的链表头部插入数据并显示 7.带头结…

5.6 Mybatis代码生成器Mybatis Generator (MBG)实战详解

文章目录 前言一、Mybatis Generator简介二、Maven插件运行方式三、生成配置 generatorConfig.xml MyBatis3Simple风格MyBatis3风格MyBatis3DynamicSql风格 四、Java代码运行方式五、MGB生成全部表六、增加Ext包七、Git提交总结 前言 本文我们主要实战Mybatis官方的代码生成器…

DeepSeek:全栈开发者视角下的AI革命者

目录​​​​​​​ DeepSeek&#xff1a;全栈开发者视角下的AI革命者 写在前面 一、DeepSeek的诞生与定位 二、DeepSeek技术架构的颠覆性突破 1、解构算力霸权&#xff1a;从MoE架构到内存革命 2、多模态扩展的技术纵深 3、算法范式的升维重构 4、重构AI竞争规则 三、…

(篇一)基于PyDracula搭建一个深度学习的界面之添加启动界面

文章目录 基于PyDracula搭建一个深度学习的界面插入一个启动界面1启动页面的资源如何加载与管理&#xff1f;2启动界面的代码如何写&#xff1f; 基于PyDracula搭建一个深度学习的界面 插入一个启动界面 1启动页面的资源如何加载与管理&#xff1f; 1. 问题一 启动界面包含一…

无人机图传模块 wfb-ng openipc-fpv,4G

openipc 的定位是为各种模块提供底层的驱动和linux最小系统&#xff0c;openipc 是采用buildroot系统编译而成&#xff0c;因此二次开发能力有点麻烦。为啥openipc 会用于无人机图传呢&#xff1f;因为openipc可以将现有的网络摄像头ip-camera模块直接利用起来&#xff0c;从而…

拍照对比,X70 PRO与X90 PRO+的细节差异

以下是局部截图&#xff08;上X70P下X90PP&#xff09; 对比1 这里看不出差异。 对比2 X90PP的字明显更清楚。 对比3 中下的字&#xff0c;X90PP显然更清楚。