動態(tài)規(guī)劃

背包問題

問題：
假設(shè)你要去野營。你有一個容量為6磅的背包，需要決定該攜帶下面的哪些東西。其中每樣東西都有相應的價值，價值越大意味著越重要：

• 水（重3磅，價值10）；
• 書（重1磅，價值3）；
• 食物（重2磅，價值9）；
• 夾克（重2磅，價值5）；
• 相機（重1磅， 價值6）。
  請問攜帶哪些東西時價值最高？

畫網(wǎng)格每一個網(wǎng)格代表一磅
cell[i][j] = max{1. 上一個單元格的值(即cell[i-1][j]的值) vs 2.當前商品的價值 + 剩余空間的價值(cell[i-1][j-當前商品的重量])}

代碼

#動態(tài)規(guī)劃
import numpy as np

#定義重量
weight = {}
weight["water"] = 3
weight["book"] = 1
weight["food"] = 2
weight["jacket"] = 2
weight["camera"] = 1
#定義價值
worth={}
worth["water"] = 10
worth["book"] = 3
worth["food"] = 9
worth["jacket"] = 5
worth["camera"] = 6

#存放行標對應的物品名
table_name={}
table_name[0] = "water"
table_name[1] = "book"
table_name[2] = "food"
table_name[3] = "jacket"
table_name[4] = "camera"

#創(chuàng)建矩陣，用來保存價值表
table = np.zeros((len(weight),6))

#創(chuàng)建矩陣，用來保存每個單元格中的價值是如何得到的（物品名）
table_class = np.zeros((len(weight),6), dtype=np.dtype((np.str_,500)))

for i in range(0,len(weight)):
    for j in range(0,6):
        #獲取重量
        this_weight = weight[table_name[i]]
        #獲得價值
        this_worth = worth[table_name[i]]
        #獲取上一個單元格(i-1,j)的值
        if(i>0):
            before_worth = table[i-1,j]
            #獲取(i-1,j-當前商品的重量)
            temp = 0
            if(this_weight<=j):
                temp = table[i-1,j-this_weight]
            #(i-1,j - this_weight)+當前商品的價值
            #判斷this_worth能不能用，即重量有沒有超標，如果重量超標了是不能加的
            synthesize_worth = 0
            if(this_weight-1<=j):
                synthesize_worth = this_worth + temp
            #與上一個單元格比較，哪個大寫入哪個
            if(synthesize_worth>before_worth):
                table[i,j] = synthesize_worth
                if(temp==0):
                    table_class[i][j] = table_name[i]
                else:
                    #他自己和(i-1,j - this_weight)
                    table_class[i][j] = table_name[i] + "," + table_class[i-1][j-this_weight]
            else:
                table[i,j] = before_worth
                table_class[i][j] = table_class[i-1][j]
        else:
            #沒有(i-1,j)那更沒有(i-1,j-重量),就等于當前商品價值，或者重量不夠，是0
            if(this_weight-1<=j):
                table[i,j] = this_worth
                table_class[i][j] = table_name[i]

print(table)

print("---------------------------------------------")

print(table_class)

運行結(jié)果

[[  0.   0.  10.  10.  10.  10.]
 [  3.   3.  10.  13.  13.  13.]
 [  3.   9.  12.  13.  19.  22.]
 [  3.   9.  12.  14.  19.  22.]
 [  6.   9.  15.  18.  20.  25.]]
---------------------------------------------
[['' '' 'water' 'water' 'water' 'water']
 ['book' 'book' 'water' 'book,water' 'book,water' 'book,water']
 ['book' 'food' 'food,book' 'book,water' 'food,water' 'food,book,water']
 ['book' 'food' 'food,book' 'jacket,food' 'food,water' 'food,book,water']
 ['camera' 'food' 'camera,food' 'camera,food,book' 'camera,jacket,food'
  'camera,food,water']]