一个包可以背4kg的东西，现在有四件东西，重量分别为1kg，4kg，3kg，1kg，价值为：1500,3000,2000,2000；
现在要求你，在包里背的东西价值最大，但是不能超过背包的最大载重量
#几件物品的重量
w = [0,1,4,3,1]
#几件物品的价值
v= [0, 1500, 3000, 2000, 2000]
#物品数量
n = len(w) - 1
#包的载重量
m = 4
#建立一个列表表示在包中的物品，元素是True时代表对应元素放入
x = []
#放入包中的总价值
value = 0
#建立一个矩阵，来表示在前i个物品中，当载重量是j时，放入包中的最大价值，table[i][j]
table = [[0 for i in range(m+1)] for j in range(n+1)]
def dynamic(w,v,n,m,x):
#计算table矩阵
for i in range(1, n+1): #代表物品一件一件的考虑
for j in range(1, m+1): #代表子背包的大小一点一点的考虑
if (j >= w[i]): #当背包的大小大于物品的重量时，考虑放进去
table[i][j] = max(table[i-1][j], table[i-1][j-w[i]] + v[i])
else:
table[i][j] = table[i -1][j] #如果放不进去，就继承之前的价值
#递推装入背包中的物体，寻找跳变的地方，从最后结果开始逆推
j = m
for i in range(n, 0, -1):
if table[i][j] > table[i- 1][j]: #如果多加一件物品之后，价值增大，就将这一件物品加入列表中
x.append(i)
j = j - w[i] #此时为剩余背包的载重量
#返回最大价值，即表格中最后一行最后一列的值
value = table[n][m]
return value
print("最大价值为：", str(dynamic(w, v, n, m, x)))
print("物品的索引：", x)
PS：python动态规划之背包问题
import numpy as np
def bag(weight,values,weight_cont):
num = len(weight)
weight.insert(0,0)
values.insert(0,0)
bag = np.zeros((num+1,weight_cont+1),dtype=np.int)
for i in range(1,num+1):
for j in range(1,weight_cont+1):
if j >= weight[i]:
bag[i][j] = max(bag[i-1][j],bag[i-1][j-weight[i]]+values[i])
else:
bag[i][j] = bag[i][j-1]
return bag[-1][-1]
if __name__ == '__main__':
weight = [1, 2, 4, 10, 12]
values = [1200, 1500, 2000, 1300, 2500]
weight_cont = 20
re = bag(weight,values,weight_cont)
print(re)
到此这篇关于python实现动态规划背包问题的文章就介绍到这了,更多相关python动态规划背包内容请搜索呐喊教程以前的文章或继续浏览下面的相关文章希望大家以后多多支持呐喊教程！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：notice#nhooo.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。