当前位置: 首页 > 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;
    }
    
http://www.lryc.cn/news/337484.html

相关文章:

  • 深度学习500问——Chapter07:生成对抗网络(GAN)(2)
  • A13 STM32_HAL库函数 之 HAL-ETH通用驱动 -- B -- 所有函数的介绍及使用
  • Qotom Q720G5英特尔赛扬处理器N4000高性价比无风扇迷你电脑5网口软路由防火墙
  • 如何了解数字化和信息化的区别?
  • CTF-SHOW SSRF
  • 客户端传日期格式字段(String),服务端接口使用java.util.Date类型接收报错问题
  • 【Python面试题收录】什么是堆?什么是栈?栈和堆的区别是什么?
  • 5-云原生监控体系-Grafana-使用配置文件实现自动化导入Dashboard
  • Ollama、FastGPT大模型RAG结合使用案例
  • 夯实智慧新能源数据底座,TiDB Serverless 在 Sandisolar+ 的应用实践
  • MySQL数据库max_allowed_packet参数
  • Day98:云上攻防-云原生篇K8s安全Config泄漏Etcd存储Dashboard鉴权Proxy暴露
  • JUC下面常见的锁
  • Uniapp+基于百度智能云完成AI视觉功能(附前端思路)
  • Android 软件盘的弹出和消失的监听
  • 通俗易懂HTTP和HTTPS区别
  • 【ZZULIOJ】1061: 顺序输出各位数字(Java)
  • java数据结构与算法刷题-----LeetCode260. 只出现一次的数字 III
  • AWS被误扣费了,怎么解决?
  • 再传IPO消息,SHEIN的上市为何充满变数?
  • maven bom
  • 若依vue中关于字典的使用
  • 链表题(哑结点的使用)
  • C#:求三个整数的最大值
  • 广州南沙番禺联想SR530服务器主板传感器故障维修
  • 深入探索自然语言处理:用Python和BERT构建文本分类模型
  • 在Visual Studio Code中编辑React项目时,以下是一些推荐的扩展
  • 智算时代的基础设施如何实现可继承可演进?浪潮云海发布 InCloud OS V8 新一代架构平台
  • LDF、DBC、BIN、HEX、S19、BLF、ARXML、slx等
  • 因为使用ArrayList.removeAll(List list)导致的机器重启