Python基于动态规划算法解决01背包问题实例
作者:littlethunder 时间:2021-01-10 21:22:26
本文实例讲述了Python基于动态规划算法解决01背包问题。分享给大家供大家参考,具体如下:
在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决。n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来:
然后自底向上实现,代码如下:
def bag(n,c,w,v):
res=[[-1 for j in range(c+1)] for i in range(n+1)]
for j in range(c+1):
res[0][j]=0
for i in range(1,n+1):
for j in range(1,c+1):
res[i][j]=res[i-1][j]
if j>=w[i-1] and res[i][j]<res[i-1][j-w[i-1]]+v[i-1]:
res[i][j]=res[i-1][j-w[i-1]]+v[i-1]
return res
def show(n,c,w,res):
print('最大价值为:',res[n][c])
x=[False for i in range(n)]
j=c
for i in range(1,n+1):
if res[i][j]>res[i-1][j]:
x[i-1]=True
j-=w[i-1]
print('选择的物品为:')
for i in range(n):
if x[i]:
print('第',i,'个,',end='')
print('')
if __name__=='__main__':
n=5
c=10
w=[2,2,6,5,4]
v=[6,3,5,4,6]
res=bag(n,c,w,v)
show(n,c,w,res)
输出结果如下:
希望本文所述对大家Python程序设计有所帮助。
来源:http://blog.csdn.net/littlethunder/article/details/26575417
标签:Python,动态规划,背包问题
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
python统计文本字符串里单词出现频率的方法
2021-11-10 17:38:48
浅谈Python3中strip()、lstrip()、rstrip()用法详解
2021-04-13 04:18:00
用Python+OpenCV对比图像质量的几种方法
2022-06-28 10:57:59
![](https://img.aspxhome.com/file/2023/1/66821_0s.png)
判断python字典中key是否存在的两种方法
2023-08-19 00:18:05
Python开发.exe小工具的详细步骤
2021-07-11 10:49:30
![](https://img.aspxhome.com/file/2023/4/94074_0s.png)
Python pygame项目实战英雄动画特效实现
2021-02-22 21:07:50
![](https://img.aspxhome.com/file/2023/0/70760_0s.png)
教你如何使用Python selenium
2022-05-15 11:13:50
python集合比较(交集,并集,差集)方法详解
2023-09-30 22:11:13
PHP addAttribute()函数讲解
2023-06-06 09:03:45
![](https://img.aspxhome.com/file/2023/2/55412_0s.png)
关于Python中request发送post请求传递json参数的问题
2022-12-23 06:20:33
![](https://img.aspxhome.com/file/2023/8/104398_0s.png)
Django压缩静态文件的实现方法详析
2023-06-15 05:31:33
导入pytorch时libmkl_intel_lp64.so找不到问题解决
2021-03-21 01:52:23
js 采用delete实现继承示例代码
2023-07-17 09:06:52
python GUI库图形界面开发之PyQt5窗口背景与不规则窗口实例
2022-05-05 02:25:04
![](https://img.aspxhome.com/file/2023/2/83752_0s.png)
Python入门教程(八)PythonCasting用法
2021-11-14 02:20:41
![](https://img.aspxhome.com/file/2023/2/81522_0s.png)
对用户研究实践的思考
2010-10-19 12:21:00
![](https://img.aspxhome.com/file/UploadPic/201010/19/01-90s.jpg)
Javascript:window对象出身何处
2007-08-28 15:16:00
Python使用Matplotlib模块时坐标轴标题中文及各种特殊符号显示方法
2021-03-12 03:38:27
![](https://img.aspxhome.com/file/2023/5/70735_0s.png)
Safari显示网页字体为超级无敌难看的宋体的原因
2008-04-20 16:49:00
在IE浏览器下面指定表单编码方式
2009-10-02 16:47:00