讨论：博物馆大盗问题
大盗潜入博物馆， 面前有5件宝物， 分别有重量和价值， 大盗的背包仅能负重20公斤， 请问如何选择宝物， 总价值最高？
我们把m(i, W)记为：
前i(1<=i<=5)个宝物中，组合不超过W(1<=W<=20) 重量，得到的最大价值m(i, W)，应该是m(i-1, W)和m(i-1, W-Wi)+vi，两者最大值我们从m(1, 1)开始计算到m(5, 20)
博物馆大盗问题：动态规划表格
递归解法
# 宝物的重量和价值
tr = {
(2, 3), (3, 4), (4, 8), (5, 8), (9, 10)}
# 大盗最大承重
max_w = 20
# 初始化记忆化表格m
# key是(宝物组合，最大重量)，value是最大价值
m = {
}
def thief(tr, w):
if tr == set() or w == 0:
m[(tuple(tr), w) in m] = 0 # tuple是key的要求
return 0
elif (tuple(tr), w) in m:
return m[(tuple(tr), w)]
else:
vmax = 0
for t in tr:
if t[0] <= w:
# 逐个从集合中去掉某个宝物，递归调用
# 选出所有价值中的最大值
v = thief(tr-{
t}, w-t[0]) + t[1]
vmax=max(vmax, v)
m[(tuple(tr), w)] = vmax
return vmax
# 输出结果
print(thief(tr, max_w))
动态规划
# 宝物的重量和价值
tr = [None, {
'w': 2, 'v': 3}, {
'w': 3, 'v': 4},
{
'w': 4, 'v': 8}, {
'w': 5, 'v': 8},
{
'w': 9, 'v': 10}
]
# 大盗最大承重
max_w = 20
# 初始化二维表格m[(i, w)]
# 表示前i个宝物中，最大重量w的组合，所得到的最大价值
# 当i什么都不取，或w上限为0，价值均为0
m = {
(i, w): 0 for i in range(len(tr)) for w in range(max_w+1)}
# 逐个填写二维表格
for i in range(1, len(tr)):
for w in range(1, max_w + 1):
if tr[i]['w'] > w: # 装不下第i个宝物
m[(i, w)] = m[(i-1), w] # 不装第i个宝物
else:
# 不装第i个宝物， 装第i个宝物，两种情况下最大价值
m[(i, w)] = max(m[(i-1, w)], m[(i-1, w-tr[i]['w'])] + tr[i]['v'])
# 输出结果
print(m[(len(tr)-1, max_w)])
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: