151、【动态规划】AcWing ——2. 01背包问题:二维数组+一维数组(C++版本)
题目描述
原题链接:2. 01背包问题
解题思路
(1)二维dp数组
动态规划五步曲:
(1)dp[i][j]的含义: 容量为j时,从物品1-物品i中取物品,可达到的最大价值
(2)递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]),其中dp[i - 1][j]表示不放物品i时的最大价值;j - v[i]表示给物品i留出空间,dp[i - 1][j - v[i]]表示给物品i留出空间后,放入其余物品可达到的最大价值(由于是按物品递增顺序遍历,因此为从1-i-1的物品),dp[i - 1][j - v[i]] + w[i]表示放入物品i和其余放入其余物品,可到达的最大价值。
(3)dp数组初始化: dp[0][j] = d[i][0] = 0, dp[0][j]中j >= v[i]的取w[i]
(4)遍历顺序: 从小到大,先背包后物品,或先物品后背包都可以。
(5)举例:
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1010;
int dp[N][N];int main(){int n, m;int v[N], w[N];cin >> n >> m;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {// 当前物品重量大于背包容量时,不放该物品if(j < v[i]) dp[i][j] = dp[i - 1][j];// 当前物品重量小于等于背包容量时,在放该物品后和不放该物品之间选择一个最大价值else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);}}cout << dp[n][m] << endl;return 0;
}
(2)优化为一维dp数组(滚动数组)
滚动数组含义:本轮所计算的数,需要用到上一轮的结果,依次类推,滚动计算。
优化成一维那就要在遍历上实现与二维相同的逻辑顺序,从而实现仅用一维就可以代替二维。
动态规划五步曲:
(1)dp[j]数组的含义: 容量为j时,装入的物品可达到的最大价值。
(2)递推公式: dp[j] = max(dp[j], dp[j - v[i]])
(3)dp数组初始化: dp[0] = 0
(4)遍历顺序: 两层for循环,先遍历物品,再遍历背包,内层按背包从大到小递减顺序遍历。
如果删除dp中的维度[i]后,还保持对j的从小到大遍历,那么此时的代码其实是等价于dp[i][j] = max(dp[i][j - 1], dp[i][j - v[i])
,在一遍后续遍历中,因为j是从小到大与v[i]相减,在后续相减时,可能会出现本轮遍历中用过的数,会使之前使用过的数重复相加。
而如果以对j进行从大到小遍历,因为此时是j
是从m
到v[i]
,以此顺序计算dp[j - v[i]]
时,在一遍后续遍历中,都是会基于上一轮对i的遍历而进行判定,并且由于j变化而v[i]不变,在后续不会出现使用过的数重复相加。每次遍历到的j所对应dp[j - v[i]]
都还没有被更新,就相当于是之前的状态dp[i - 1][j - v[i]]
,从而得到dp[j] = dp[j - v[i]]
就等价于dp[i][j] = dp[i - 1][j - v[i]]
。
(5)举例:
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1010;
int dp[N];int main(){int n, m;int v[N], w[N];cin >> n >> m;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];for(int i = 1; i <= n; i++) {// 从后向前遍历,表示装入一个物品后,剩余的可装入容量达到的最大价值for(int j = m; j >= v[i]; j--) {dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}cout << dp[m] << endl;return 0;
}
参考文章:AcWing 2. 01背包问题(状态转移方程讲解) 、AcWing 2. 01背包问题 、动态规划:关于01背包问题,你该了解这些!(滚动数组)
相关文章:

151、【动态规划】AcWing ——2. 01背包问题:二维数组+一维数组(C++版本)
题目描述 原题链接:2. 01背包问题 解题思路 (1)二维dp数组 动态规划五步曲: (1)dp[i][j]的含义: 容量为j时,从物品1-物品i中取物品,可达到的最大价值 (2…...

DS期末复习卷(二)
选择题 1.下面关于线性表的叙述错误的是( D )。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 © 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插…...

大数据技术架构(组件)31——Spark:Optimize--->JVM On Compute
2.1.9.4、Optimize--->JVM On Compute首要的一个问题就是GC,那么先来了解下其原理:1、内存管理其实就是对象的管理,包括对象的分配和释放,如果显式的释放对象,只要把该对象赋值为null,即该对象变为不可达.GC将负责回…...

ETL基础概念及要求详解
ETL基础概念及要求详解概念ETL与ELT数据湖与数据仓库ETL应用场景ETL具体流程及操作要求抽取清洗转换加载ETL设计模式SQL脚本语言ETL工具设计ETL工具SQLETL接口设计要求明确接口属性约定接口形式确定接口抽取方法规范接口格式概念 ETL即Extract(抽取)Tra…...
刷题记录:牛客NC23054华华开始学信息学 线段树+分块
传送门:牛客 题目描述: 题目latex公式较多,此处省略 输入: 10 6 1 1 1 2 4 6 1 3 2 2 5 7 1 6 10 2 1 10 输出: 3 5 26这道题让我体验到的线段树相对于树状数组的常数巨大 我们倘若直接用单点修改的话,如果D过小比如1那么我们足足要加n次,时间复杂度爆…...

二叉搜索树(查找,插入,删除)
目录 1.概念 2.性质 3.二叉搜索树的操作 1.查找 2.插入 3.删除(难点) 1.概念 二叉搜索树又称二叉排序树.利用中序遍历它就是一个有顺序的一组数. 2.性质 1.若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 2.若它的右子树不为空,则右子树上所有节点的值都…...
C# PictureEdit 加载图片
方法一: 如果要加载的图片的长宽比不是太过失衡, 1.可以改变picturebox的SizeMode属性为 PictureBoxSizeMode.StretchImage, 2.或者Dev控件 PictureEdit的SizeMode属性为Zoom。(zoom:缩放;clip剪短;stret…...

3种方法设置PDF“打开密码”,总有一种适合你
PDF文件是我们工作中经常用到的文件之一,对于重要的文件,设置“打开密码”是一种很好的保护方式。下面就来说说,设置PDF“打开密码”有哪三种方法? 方法一:在线网站加密 市面上有很多可以直接在线上加密PDF文件的产品…...
第三章 数据链路层(点到点的传输服务)-计算机网络(笔记)
计算机网络 第三章 数据链路层(点到点的传输服务) 数据链路层属于计算机网络的低层。数据链路层使用的信道主要有以下两种类型: (1)点到点信道。这种信道使用一对一的点到点通信方式。 (2)广…...
volatile关键字与CAS机制
volatile关键字 volatile关键字可以对类的成员变量与静态变量进行修饰 volatile关键字的作用 1.保证被修饰属性的可见性,被修饰后的属性如果被更改后其他线程是会立即可见的 2.保证被修饰属性的有序性,被修饰后的属性禁止修改指令执行的顺序 注意:volatile关键字不能保证属性…...

LeetCode题解 动态规划(四):416 分割等和子集;1049 最后一块石头的重量 II
背包问题 下图将背包问题做了分类 其中之重点,是01背包,即一堆物件选哪样不选哪样放入背包里。难度在于,以前的状态转移,多只用考虑一个变量,比如爬楼梯的阶层,路径点的选择,这也是能用滚动数组…...

【FFMPEG源码分析】从ffplay源码摸清ffmpeg框架(二)
demux模块 从前面一篇文章中可以得知,demux模块的使用方法大致如下: 分配AVFormatContext通过avformat_open_input(…)传入AVFormatContext指针和文件路径,启动demux通过av_read_frame(…) 从AVFormatContext中读取demux后的audio/video/subtitle数据包…...

PCIE 学习笔记(入门简介)
PCIE 学习笔记书到用时方恨少啊,一年前学PCIE的笔记,再拿出来瞅瞅。发到博客上,方便看。PCIE基础PCIE和PCI的不同PCIE采用差分信号传输,并且是dual-simplex传输——每条lane上有TX通道和RX通道,所以每条lane上的信号是…...

锁的优化机制了解嘛?请进!
点个关注,必回关 文章目录自旋锁:自适应锁:锁消除:锁粗化:偏向锁:轻量级锁:从JDK1.6版本之后,synchronized本身也在不断优化锁的机制,有些情况下他并不会是一个很重量级的…...

5.点赞功能 Redis
Redis(1)简介Redis 是一个高性能的 key-value 数据库原子 – Redis的所有操作都是原子性的。多个操作也支持事务,即原子性,通过MULTI和EXEC指令包起来。非关系形数据库数据全部存在内存中,性能高。(2&#…...
Java序列化和反序列化(详解)
一、理解Java序列化和反序列化 Serialization(序列化):将java对象以一连串的字节保存在磁盘文件中的过程,也可以说是保存java对象状态的过程。序列化可以将数据永久保存在磁盘上(通常保存在文件中)。 deserialization(反序列化):将保存在磁…...

【刷题篇】链表(上)
前言🌈前段时间我们学习了单向链表和双向链表,本期将带来3道与链表相关的OJ题来巩固对链表的理解。话不多说,让我们进入今天的题目吧!🚀本期的题目有:反转单链表、链表的中间结点、合并两个有序链表反转单链…...
ConcurrentHashMap设计思路
ConcurrentHashMap设计思路Hashtable vs ConcurrentHashMapHashtable vs ConcurrentHashMap Hashtable 对比 ConcurrentHashMap Hashtable 与 ConcurrentHashMap 都是线程安全的 Map 集合Hashtable 并发度低,整个 Hashtable 对应一把锁,同一时刻&#…...

Unity基于GraphView的行为树编辑器
这里写自定义目录标题概述基于GitHub上:目前这只是做了一些比较基础的功能节点开发,仅仅用于学习交流,非完成品。项目GitHub连接:[https://github.com/HengyuanLee/BehaviorTreeExamples](https://github.com/HengyuanLee/Behavio…...

网络流量传输MTU解析
基本概念 以太网的链路层对数据帧的长度会有一个限制,其最大值默认是1500字节,链路层的这个特性称为MTU,即最大传输单元 Maximum Transmission Unit,最大传输单元,指的是数据链路层的最大payload,由硬件网…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...

Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...