4.動態(tài)規(guī)劃 0/1背包問題實(shí)例學(xué)習(xí)
比如，有三件物品重量w,價(jià)值v分別是
w=[5,3,2]
v=[9,7,8]
包的容量是5，也就是我們要求得
maxVal=v1+v2+v3……
約束條件為：ws=w1+w2+w3……
解題思路是，列舉出所有可能的放入背包的選項(xiàng)，然后比較哪個價(jià)值大，這需要用到?jīng)Q策樹。
決策樹的思想是，用一組向量來描述當(dāng)前的狀態(tài)，比如，當(dāng)前考慮的物品i, 當(dāng)前背包的空間w， 當(dāng)前已獲得的價(jià)值v
決策樹左兒子表示不選取當(dāng)前物品np，右兒子表示選取當(dāng)前物品p，首先遞歸到索引為最后一個的物品，然后回溯，每回溯到一個物品時候就比較選取當(dāng)前物品和不選取當(dāng)前物品哪個更有價(jià)值
1 memo={}
2 def maxVal(w, v, i, ws):
3 try: 4 return memo[(i,ws)]
5 except KeyError:
6 if i == 0: 7 if w[i] <= ws:
8 memo[(i, ws)] = v[i]
9 return v[i]
10 else:
11 memo[(i, ws)] = 0
12 return 0
13 without_i = maxVal(w, v, i-1, ws)
14 if w[i] > ws:
15 memo[(i, ws)] = without_i
16 return without_i
17 else:
18 with_i = maxVal(w, v, i-1, ws-w[i]) + v[i]
19 res = max(without_i, with_i)
20 memo[(i, ws)] = res
21 return res
22 w = [5, 3, 2]
23 v = [9, 7, 8]
24 val = maxVal(w, v, 2, 5)
25 print(val)
參考博客：https://www.cnblogs.com/fcyworld/p/6243012.html
5.0/1背包問題練習(xí)
def maxVal(toConsider, avail):
if toConsider == [] or avail == 0:
result = (0, ())
elif toConsider[0].getWeight() > avail:
#查詢右側(cè)分支
result = maxVal(toConsider[1:], avail)
else:
nextItem = toConsider[0]
#查詢左側(cè)分支
withVal, withToTake = maxVal(toConsider[1:],
avail - nextItem.getWeight())
withVal += nextItem.getValue()
#查詢右側(cè)分支
withoutVal, withoutToTake = maxVal(toConsider[1:], avail)
#選擇更好的分支
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
return result
