博物館大盜問題的動態規劃

博物館大盜問題

大盜潛入博物館,面前有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))