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

【01背包】滚动数组优化实现一维01背包DP(对比朴素写法)

01背包

代码

背包问题的滚动数组优化版本建议在完全弄懂了普通的二维01背包问题后再进行食用,不然会出现消化不良的症状…

我们可以将背包问题中DP数组的下标看作成两个集合

下面对比两种不同实现方法的区别:

  • 朴素二维DP版本

    • 使用dp[不超过i的物品集合][不超过j的背包集合]
    • 我们会发现,每次使用的[不超过第i个物品的集合]只会是ii-1,再往前的集合在后续的计算都不会被使用,所以可以采用滚动数组的思想,不断的更新一个一维数组来达到相同的目的。
    • 同时,我们每次会对每一个物品寻找所有[不超过j的背包的集合],如果背包放不下这个物品,直接继承没有放i物品的状态即可,也就是[不超过i-1位物品]的集合。
    • 同时这里和优化版本的区别还在于遍历顺序,朴素版本不用考虑遍历顺序,但是优化版本需要注意。
    #include <iostream>
    using namespace std;
    // DP-normal-wayconst int N = 1010;
    int n, m;		//n件物品 m容量的背包 
    int v[N], w[N]; //每件物品的体积 价值 
    int f[N][N];	//f[i][j]不超过第i件物品 背包容量不超过j /*
    4 5
    1 2
    2 4
    3 4
    4 5
    */int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];			//输入体积 价值 }//f[0][0~m]默认为零,无需进行初始化for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (j >= v[i]) f[i][j] = max(f[i-1][j], w[i] + f[i-1][j-v[i]]);else f[i][j] = f[i-1][j];}} 	cout << f[n][m] << endl;	
    }
    
  • 滚动数组优化版本 --> 一维DP(01背包问题终极写法)

    • dp[i][j]-->dp[j]删掉了i这个集合,相当于现在每次只存放了前一个物品的[背包不超过j]的最大值。
      • 比如第一次,dp[]存放的是不超过第一个物品的[背包不超过j] 的最大值。
      • 第二次在第一次的基础上进行更新,这里需要注意背包集合的遍历顺序,需要思考如果还是正序遍历会带来什么影响?
      • 没错,因为每次都要利用到之前的[背包不超过j]的集合,如果正序遍历,那么就会从小的背包开始更新,那么就会把上一次的背包最大值覆盖掉,遍历到后面,j大起来了,要使用上一次也就是[物品不超过i-1][背包不超过j]的集合来进行更新就会碰到滚动数组数据被覆盖了的问题。
      • 所以,需要注意的就是,要从大的背包开始遍历j,这样就可以避免dp[背包容量<j]被覆盖掉,进行滚动的更新。
    #include <iostream>
    // 01背包1维写法 const int N = 10010;
    int n, m;	//物品个数  背包容量
    int v[N], w[N];	//每个物品的:体积 价值
    int dp[N];	//优化前:不超过i的物品的体积和不超过j的背包 --> 优化后: 不超过i件物品  -->最大价值 
    /*输入数据不变: 
    4 5
    1 2
    2 4
    3 4
    4 5
    */
    using namespace std;int main() {cin >> n >> m;for (int i = 0; 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;
    }
    

相关文章:

【01背包】滚动数组优化实现一维01背包DP(对比朴素写法)

01背包 代码 背包问题的滚动数组优化版本建议在完全弄懂了普通的二维01背包问题后再进行食用&#xff0c;不然会出现消化不良的症状… 我们可以将背包问题中DP数组的下标看作成两个集合 下面对比两种不同实现方法的区别&#xff1a; 朴素二维DP版本 使用dp[不超过i的物品集合]…...

深度学习500问——Chapter07:生成对抗网络(GAN)(2)

文章目录 7.2 GAN的生成能力评价 7.2.1 如何客观评价GAN的生成能力 7.2.2 Inception Score 7.2.3 Mode Score 7.2.5 Wasserstein distance 7.2.6 Frchet Inception Distance (FID) 7.2.7 1-Nearest Neighbor classifier 7.2.8 其他评价方法 7.3 其他常见的生成式模型有哪些 7.…...

A13 STM32_HAL库函数 之 HAL-ETH通用驱动 -- B -- 所有函数的介绍及使用

A13 STM32_HAL库函数 之 HAL-ETH通用驱动 -- B -- 所有函数的介绍及使用 1 通用定时器&#xff08;TIM&#xff09;预览1.11 HAL_ETH_TxCpltCallback1.12 HAL_ETH_RxCpltCallback1.13 HAL_ETH_ErrorCallback1.14 HAL_ETH_ReadPHYRegister1.15 HAL_ETH_WritePHYRegister1.16 HAL…...

Qotom Q720G5英特尔赛扬处理器N4000高性价比无风扇迷你电脑5网口软路由防火墙

在数字时代&#xff0c;迷你电脑已经成为高效、灵活的解决方案&#xff0c;无论是个人用户还是企业用户&#xff0c;都能从中受益。Qotom Q720G5 无风扇迷你电脑就是这样一款强大的选择&#xff0c;它不仅可以作为软路由、防火墙和路由器&#xff0c;还有着更多的潜力等待发掘。…...

如何了解数字化和信息化的区别?

在数字化浪潮席卷全球的今天&#xff0c;企业如何乘风破浪、实现转型升级&#xff1f; 数字化和信息化&#xff0c;这两个看似相似却各有千秋的概念&#xff0c;一直被人们拿来对比。 下面就来讲一讲我的理解&#xff1a; 从简单了说&#xff1a; “信息化”可以理解为传统数…...

CTF-SHOW SSRF

web351 存在一个flag.php页面&#xff0c;访问会返回不是本地用户的消息&#xff0c;那肯定是要让我们以本地用户去访问127.0.0.1/flag.php web352 代码中先判断是否为HTTP或https协议&#xff0c;之后判断我们传入的url中是否含有localhost和127.0.0&#xff0c;如果没有则…...

客户端传日期格式字段(String),服务端接口使用java.util.Date类型接收报错问题

客户端传日期格式字段&#xff08;string&#xff09;,服务端接口使用java.util.Date类型接收报错问题 问题演示第1种&#xff1a;客户端以URL拼接的方式传值第2种&#xff1a;客户端以body中的form-data方式提交第3种 客户端以Body中的json方式提交 问题解决&#xff08;全局解…...

【Python面试题收录】什么是堆?什么是栈?栈和堆的区别是什么?

一、堆和栈的定义 &#xff08;1&#xff09;堆&#xff08;Heap&#xff09; 数据结构&#xff1a;堆是一种特殊的完全二叉树&#xff0c;满足父节点的值总是大于或等于&#xff08;大根堆&#xff09;其子节点的值。也可以是总是小于或等于&#xff08;小根堆&#xff09;其…...

5-云原生监控体系-Grafana-使用配置文件实现自动化导入Dashboard

文章目录 1. 介绍(此文档使用的版本 grafana-enterprise-10.0.3-1)2. 清空之前的实验数据3. 使用配置文件方式配置 Datasource3.1. 创建配置文件3.2. 重启服务并检查是否生效4. 使用配置文件方式配置 Dashboard4.1. 创建配置文件5. 配置 Dashboard JSON 文件5.1. 下载 JSON 文…...

Ollama、FastGPT大模型RAG结合使用案例

参考: https://ollama.com/download/linux https://doc.fastai.site/docs/intro/ https://blog.csdn.net/m0_71142057/article/details/136738997 https://doc.fastgpt.run/docs/development/custom-models/m3e/ Ollama作为后端大模型加载运行 FastGPT作为前端页面聊天集成RA…...

夯实智慧新能源数据底座,TiDB Serverless 在 Sandisolar+ 的应用实践

本文介绍了 SandiSolar通过 TiDB Serverless 构建智慧新能源数据底座的思路与实践。作为一家致力于为全球提供清洁电力解决方案的新能源企业&#xff0c;SandiSolar面临着处理大量实时数据的挑战。为了应对这一问题&#xff0c;SandiSolar选择了 TiDB Serverless 作为他们的数据…...

MySQL数据库max_allowed_packet参数

如上图所示的报错&#xff0c;我在提交接口的时候出现了这个错误&#xff1a; MySqlConnector.MySqlException:Error submitting 4MB packet;ensure max_allowed_packet is greater than 4MB.在MySQL数据库中&#xff0c;有一个参数叫max_allowed_packet&#xff0c;这个参数会…...

Day98:云上攻防-云原生篇K8s安全Config泄漏Etcd存储Dashboard鉴权Proxy暴露

目录 云原生-K8s安全-etcd(Master-数据库)未授权访问 etcdV2版本利用 etcdV3版本利用 云原生-K8s安全-Dashboard(Master-web面板)未授权访问 云原生-K8s安全-Configfile鉴权文件泄漏 云原生-K8s安全-Kubectl Proxy不安全配置 知识点&#xff1a; 1、云原生-K8s安全-etcd未…...

JUC下面常见的锁

这里写目录标题 1、ReentrantLock2、Semaphore3、CountDownLatch4、CyclicBarrier 1、ReentrantLock ReentrantLock 是属于独占模式&#xff0c; 即同一时刻只允许一个线程获取锁。 2、Semaphore Semaphore 属于共享模式&#xff0c;synchronized 和 ReentrantLock 都是一次只…...

Uniapp+基于百度智能云完成AI视觉功能(附前端思路)

本博客使用uniapp百度智能云图像大模型中的AI视觉API&#xff08;本文以物体检测为例&#xff09;完成了一个简单的图像识别页面&#xff0c;调用百度智能云API可以实现快速训练模型并且部署的效果。 uniapp百度智能云AI视觉页面实现 先上效果图实现过程百度智能云Easy DL训练图…...

Android 软件盘的弹出和消失的监听

监听接口 OnKeyboardListener.java public interface OnKeyboardListener {void onKeyboardHidden();void onKeyboardShow(int keyboardHeight);} KeyBoardUtil.java public class KeyBoardUtil {private final static String TAG "KeyBoardUtil";public PopupWi…...

通俗易懂HTTP和HTTPS区别

HTTP&#xff1a;超文本传输协议&#xff0c;它是使用一种明文的方式发送我们的内容&#xff0c;没有任何的加密&#xff0c;例如我们要在网页上输入账号密码&#xff0c;如果使用HTTP协议&#xff0c;账号密码就可能会被暴露&#xff0c;默认端口是80. HTTPS&#xff1a;是HT…...

【ZZULIOJ】1061: 顺序输出各位数字(Java)

目录 题目描述 输入 输出 样例输入 Copy 样例输出 Copy 提示 code 题目描述 输入一个不大于10的9次方的正整数&#xff0c;从高位开始逐位分割并输出各位数字。 输入 输入一个正整数n,n是int型数据 输出 依次输出各位上的数字&#xff0c;每一个数字后面有一个空格…...

java数据结构与算法刷题-----LeetCode260. 只出现一次的数字 III

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 与运算取末尾1分组 与运算取末尾1分组 解题思路&#xff1a;时间…...

AWS被误扣费了,怎么解决?

有时在使用aws时&#xff0c;可能会无意中被AWS扣费&#xff0c;对于如何处理这个问题&#xff0c;作为aws的合作伙伴&#xff0c;接下来由九河云进行讲解&#xff1a; &#xff08;1&#xff09;审查账单&#xff1a;首先&#xff0c;您需要仔细审查AWS账单&#xff0c;了解具…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

渗透实战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…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...