動态規劃在計算機算法中算是一類比較難的問題。 這個問題的難點在于如何抽象出狀态,根據狀态抽象出狀态轉移方程。
動态規劃中經典的問題是0-1背包問題，題目的很簡單，有N個物品，每個物品的重量是Wi, 物品的價值是Vi， 有一個容量為maxW的背包，問這個背包中能裝下物品的最大價值是多少。
那就是對于每一個物品， 有兩個可能性，要麼裝進去，要麼不裝。 可以分析一下這兩種情況。
裝進去： 1. 背包的剩餘空間能裝下該物品。 2. 裝下該物品可以使背包的總價值增大（成本效益高）。
不裝： 1. 裝不進去，剩餘空間不夠。 2. 剩餘空間夠，但是不能使背包的總價值增大（成本效益不高）。
是以我們可以得到這樣一個狀态轉移的方程：
dp[i][j] = max(dp[i-1][j], dp[i - 1][j - Wi] + Vi) 注意： j - Wi >= 0
dp 的行是物品的數量， 列是背包的容量。 這個方程就是上面解釋的，滿足條件，并且可以使背包的價值增大才能裝下該物品。
看一下python實作的背包算法。
def package_problem(weight, value, max_weight):
n = len(weight) + 1
m = max_weight + 1
dq = [[0 for j in range(m)] for i in range(n)]
path = [-1] * (n - 1)
for i in range(1, n):
for j in range(m):
if j - weight[i - 1] >= 0:
dq[i][j] = max(dq[i-1][j], dq[i-1][j - weight[i - 1]] + value[i - 1])
max_value = dq[len(weight)][max_weight]
last = m-1
for i in range(n-1, 0, -1):
for j in range(last, 0, -1):
if j - weight[i - 1] >= 0:
if dq[i][j] == dq[i - 1][j - weight[i-1]] + value[i - 1]:
path[i - 1] = i - 1
last = j - weight[i-1]
break
print(path)
return max_value
if __name__ == '__main__':
weight = [0,4, 1, 1,3]
value = [0,3000,2000,1500,2000]
max_weight = 5
ret = package_problem(weight, value, max_weight)
print(ret) 複制
輸出結果:
[-1, -1, 2, 3, 4]
5500
更多内容請關注： IT技術漫漫談