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

01 背包问题解析与代码 python 实现

01 背包问题解析与代码

问题定义

给定一堆具有不同重量 { w 1 , w 2 , ⋯ , w n } \{ w_1,w_2, \cdots,w_n \} {w1,w2,,wn}与价值 { v 1 , v 2 , ⋯ , v n } \{ v_1,v_2, \cdots,v_n \} {v1,v2,,vn}的背包(knapsack),在总重量为 W 的情况下,如何选取背包才能获得最大价值?其中每种背包只能有被选取和不被选取两种选择。

思路解析

考虑解数组 d p [ i ] [ j ] dp[i][j] dp[i][j] ,其中的 i i i 表示尝试放入标号为 1 到 i 的背包, j j j 表示当前的限重为 j j j,数组中的值表示当前情况下可以取得的最大价值。

显然这个 dp 数组的第一行和第一列元素全为 0,逐个计算时我们使用从左到右,从上到下的原则进行计算,在计算 d p [ i ] [ j ] dp[i][j] dp[i][j] 时,需要考虑两种情况:

第一种当前的总限重是不允许放入标号为 i 的背包的,也就是当前总限重小于标号为 i 的背包的重量,那么此时的最大价值应该等于总限重为 j,且尝试放入标号为 1-(i-1) 背包时的总价值,用公式表达:
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] ( j < w [ i ] ) dp[i][j]=dp[i-1][j](j<w[i]) dp[i][j]=dp[i1][j](j<w[i])
第二种则是当前的总限重是允许放入标号为 i 的背包的,也就是当前总限重大于标号为 i 的背包的重量,那么此时的最大价值又需要考虑两种情况,原因是放入标号为 i 的背包可能并不能取得最大价值。

放入标号为 i 的背包会产生多大的价值呢?这时我们就可以利用到先前已经计算好的解数组了,在放入标号为 i 的元素之后,背包限重变为 j - w[i],那么放入 i-1(不包含第i个) 个背包,总限重为 j - w[i] 的情况下的最大价值就是 d p [ i − 1 ] [ j − w [ i ] ] dp[i-1][j-w[i]] dp[i1][jw[i]],这时再加上标号 i 的背包总价值就是 d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] dp[i-1][j-w[i]]+v[i] dp[i1][jw[i]]+v[i]

不放入标号为i的背包的价值则为 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j]

所以,此时的最大价值应当比较上述两种情况,选取最大值
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) ( j ≥ w [ i ] ) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])(j \geq w[i]) dp[i][j]=max(dp[i1][j],dp[i1][jw[i]]+v[i])(jw[i])
这里提供一个在线练习 01背包数组填充的网站。

代码实现

def algo(weight, value, total):row = len(weight)col = total + 1res = [[0] * col for _ in range(row)]for i in range(1, row):for j in range(1, col):if weight[i] > j:res[i][j] = res[i-1][j]else:res[i][j] = max(res[i-1][j], res[i-1][j-weight[i]] + value[i])return resweight = [0, 4, 2, 3, 1]
value = [0, 9, 10, 4, 1]
total = 6print(algo(weight, value, total))
http://www.lryc.cn/news/93845.html

相关文章:

  • Vue实现前端视频展示列表及特征提取、笔记、删除、文件夹组织功能
  • 多传感器时频信号处理:多通道非平稳数据的分析工具(Matlab代码实现)
  • 数据结构算法 -分而治之算法
  • 涉密信息系统口令管理制度
  • UML与流程图
  • 音视频开发Level0: 入门级20~25k的工作
  • Git第一章、Git的原理与使用
  • 软件开发流程
  • 编程语言的优劣评选标准与未来发展趋势——探索最佳编程语言选择
  • axios 发送请求请求头信息不包含Cookie信息
  • 正则表达式笔记
  • 数据结构链表(C语言实现)
  • Springboot实现接口传输加解密
  • TypeScript类型系统:强类型的优势和使用方式
  • 有没有可以代替风铃系统的专业问卷工具?
  • 【数字调制】数字调制技术FSK与PSK分析与研究(Matlab代码实现)
  • html实现好看的个人介绍,个人主页模板4(附源码)
  • 内存不够用,那你的内存去哪了?
  • 哈希表--day4--(leetcode202/leetcode1/leetcode454)
  • 基于Python+Django+mysql+html通讯录管理系统
  • Rabbitmq学习
  • 初识轻量级分布式任务调度平台 xxl-job
  • web 语音通话 jssip
  • 随风摇曳的她——美蕨(matlab实现)
  • 时序数据库的流计算支持
  • springboot启动流程 (3) 自动装配
  • ansible-roles模块
  • 聊聊我做 NeRF-3D重建性能优化经历
  • 未磁科技全球首台64通道无液氦心磁图仪及首个培训基地落户北京安贞医院
  • SpringBoot 如何使用 ApplicationEventPublisher 发布事件