1、动态规划 0-1 背包
<pre><code>#python实现动态规划算法 求解0-1背包问题
# f 是6*16的二维数组
f = [[0 for i in range(16)] for i in range(6)]
# print(f)
# 重量 和 对应价值
weight = [3, 5, 8, 6, 7]
value = [8, 3, 4, 9, 5]
# 遍历循环求解 把前i件物品放入容量为j的背包中
# 时间复杂度 O(n*W) 这里n为5 W为15
for i in range(1,6):
for j in range(1,16):
if(j - weight[i-1] >= 0):
if(f[i-1][j] > f[i-1][j - weight[i-1]] + value[i-1]):
f[i][j] = f[i-1][j]
else:
f[i][j] = f[i - 1][(j - weight[i - 1])] + value[i - 1]
else:
f[i][j] = f[i - 1][j]
# 打印前i件物品放入容量为j的背包中的最优方案
for i in range(0,6):
for j in range(0,16):
print(str(f[i][j]) + ' ',end='')
print('')
# 输出当前问题的最优方案
print('最优方法如下：')
j = 15
for i in range(5,0,-1):
if (f[i][j] != f[i - 1][j]):
print("把物品" + str(i) + "加入背包")
j = j - weight[i - 1]
</code></pre>