動(dòng)態(tài)規(guī)劃 遞歸 Python
問題描述：在M件物品取出若干件放在空間為W的背包里，每件物品的體積為W1，W2……Wn，與之相對應(yīng)的價(jià)值為P1,P2……Pn。求出獲得最大價(jià)值的方案。
注意：在此問題中，所有的體積值均為整數(shù)。01的意思是，每個(gè)物品都是一個(gè)整體，要么整個(gè)都要，要么都不要。
- 最優(yōu)子結(jié)構(gòu)
考慮所有物品的子集合，考慮第n個(gè)物品都有兩種情況: 1. 包括在最優(yōu)方案中 2. 不在最優(yōu)方案中因此，能獲得的最大價(jià)值，即為以下兩個(gè)值中較大的那個(gè)：
- 在剩下 n-1 個(gè)物品中(剩余 W 重量可用)的情況能得到的最大價(jià)值 (即排除了 第n個(gè)物品)
- 第n個(gè)物品的價(jià)值 加上 剩下 剩下的 n-1 個(gè)物品(剩余W- wn的重量)能得到的最大價(jià)值。(即包含了第n個(gè)物品)
如果第n個(gè)物品的重量，超過了當(dāng)前的剩余重量W，那么只能選情況1)， 排除第n個(gè)物品。
由上面的最優(yōu)子結(jié)構(gòu)，可以得到一個(gè)遞歸解法：
def kanpSack_rec(W,wt,val,n):
if n==0 or W == 0:
return 0
# 如果第n個(gè)物品的重量超過背包容量W,這件物品就不能被加進(jìn)背包
if (wt[n-1] > W):
return kanpSack_rec(W,wt,val,n-1)
# 返回下面兩種情況中的最大值:
# (1) 第n個(gè)物品被放進(jìn)背包中
# (2) 沒被放進(jìn)背包
else:
return max(val[n-1]+kanpSack_rec(W-wt[n-1],wt,val,n-1),kanpSack_rec(W,wt,val,n-1))
這種方法其實(shí)就是搜索了所有的情況，但是有很多重復(fù)的計(jì)算。時(shí)間復(fù)雜度是指數(shù)級的 O(2^n)。
0-1背包滿足動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本屬性(重疊子問題和最優(yōu)子結(jié)構(gòu))。可以通過自下而上的打表，存儲(chǔ)中間結(jié)果，來避免重復(fù)計(jì)算。即：欲求前i個(gè)物體放入容量為m（kg）背包的最大價(jià)值c[i][m]——使用一個(gè)數(shù)組來存儲(chǔ)最大價(jià)值。而前i個(gè)物體放入容量為m（kg）的背包，又可以轉(zhuǎn)化成前(i-1)個(gè)物體放入背包的問題。下面使用數(shù)學(xué)表達(dá)式描述它們兩者之間的具體關(guān)系，表達(dá)式中各個(gè)符號的具體含義：
wt[i] : 第i個(gè)物體的重量
val[i] : 第i個(gè)物體的價(jià)值
K[i][w] ： 前i個(gè)物體放入容量為w的背包的最大價(jià)值
K[i-1][w] ： 前i-1個(gè)物體放入容量為w的背包的最大價(jià)值
K[i-1][W-wt[i]] ： 前i-1個(gè)物體放入容量為M-wt[i]的背包的最大價(jià)值；
由此可得：
c[i][m]=max{c[i-1][m-w[i]]+val[i] , c[i-1][m]}
解法如下：
def knapsack_norec(W,wt,val,n):
K = [[0 for x in range(W+1)] for x in range(n+1)]
# 從底向上構(gòu)建K[][]表
for i in range(n+1):
for w in range(W+1):
if i==0 or w==0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]],K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]
