博物馆大盗问题

大盗潜入博物馆,面前有5件宝物,分别有重量和价值,大盗的背包仅能负重20公斤,请问如何选择宝物,总价值最高?

m(i, W) 表示前i(1<=i<=5)个宝物中,组合不超过W(1<=W<=20) 重量,得到的最大价值。

• 第 i 件宝物重量 Wi > 背包承重 W, 那么m(i, W) = m(i-1, W);

• 第 i 件宝物重量 Wi <= 背包承重 W,

  • 如果第 i 件宝物太重,加不到背包中,那么前 i 件宝物价值等于前 i-1 件宝物价值,即 m(i, W) = m(i-1, W);
  • 如果第 i 件宝物可以加入到背包中,那么前 i 件宝物价值等于前 i-1 件宝物价值加上第 i 件宝物价值Wi,即 m(i, W) = m(i-1, W-Wi)+vi。
    因此,m(i, W) 应该是m(i-1, W) 和m(i-1, W-Wi)+vi 两者最大值,即m(i, W) = max{m(i-1, W), m(i-1, W-Wi)+vi}
    
    以m(5, 5)为例,m(5,5) = m(4,5) = max(m(3,5), m(3,0)+8), 动态规划表格如下:
    

动态规划解法代码

# 用一个列表来保存宝物的重量w和价值vtr = [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)],将表格中所有价值均初始化为0# 表示前i个宝物中,最大重量w的组合,所得到的最大价值# 当i或w为0时,价值为0m = {(i, w):0 for i in range(len(tr))                 for w in range(max_w + 1)}# 逐个填写二维表格# 外层循环为 i个宝物,[1,6)的循环# 内层循环为 重量w,[1, max_w+1)的循环for i in range(1, len(tr)):    for w in range(1, max_w + 1):        if tr[i]['w'] > w:            # 装不下第i个宝物,即不装第i个宝物            m[(i, w)] = m[(i-1, w)]        else:            # 装得下第i个宝物时,在不装第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)])

递归解法

# 用一个字典来保存宝物的重量w和价值vtr = {(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)] = 0        return 0    elif (tuple(tr), w) in m:        return m[(tuple(tr), w)]    else:        vmax = 0        for t in tr:            if t[0] <= w:                # 逐个从集合中去掉某个宝物t,递归调用                # 选出所有价值中的最大值                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))