Python动态规划算法解决01背包问题 Python基于动态规划算法解决01背包问题实例
littlethunder 人气:0想了解Python基于动态规划算法解决01背包问题实例的相关内容吗，littlethunder在本文为您仔细讲解Python动态规划算法解决01背包问题的相关知识和一些Code实例，欢迎阅读和指正，我们先划重点：Python,动态规划,算法,01背包问题，下面大家一起来学习吧。
本文实例讲述了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程序设计有所帮助。
加载全部内容