Backtracking
我们把物体依次排列,整个问题就分为n个阶段,每个阶段对应一个物品 i 怎样选择。
观察解空间树,每个结点我们用(i,cw)来表示。i表示将要觉得i个物品是否装入背包,只有装和不装两种情况。cw 表示当前背包中的重量。比如(2,2)表示我们将要觉得第2个物品是否装入背包,在决策前,背包中物品的总重量是2。
1 | weights = [2,2,4,6,3] |
Backtracking with memory
我们发现,很多子问题是重复的。比如f(2,2) 和 f(3,6)都被重复计算很多次。因此,我们可以用备忘录的方法来解决重复计算的问题。
1 | weights = [2,2,4,6,3] |
Dynamic Programming
我们把整个求解的过程分为n个阶段,每个阶段会决策一个物品是否放入背包中。每个物品决策完成后,背包中的重量会有多种情况。
动态规划问题的解决步骤一般可以总结为 3 步:
- 定义数组元素的含义
我们用 dp[n][cw] 来表示在第n个阶段重量为cw的状态。 - 找出状态转移方程。
- 把第 i 个物品装入背包中
- 不把第 i 个物品装入背包中比如第 0 个物品的重量是2,要么装入背包,要么不装入背包。决策完之后会对应背包的两种状态,背包中物品的总重量为 0 或者 2。
我们用dp[0][0] = true 和 dp[0][2] = true表示。
- 初始值。
- 第 0 个物品不装: dp[0][0] = true
- 第 0 个物品装: dp[0][weights[i]] = true
import pprint
weights = [2,2,4,6,3]
W = 9
n = 5
def dp_bag(weights,W,n):
dp = [[0] * (W+1) for i in range(n)]
## 第 0 个物品不装
dp[0][0] = 1
## 第 0 个物品装
if weights[0] < W:
dp[0][weights[0]] = 1
for i in range(1,n):
for j in range(W):
## 不把 i 放入背包中,当前背包重量不变
if dp[i-1][j]:
dp[i][j] = 1
for j in range(W):
## 把 i 放入背包中
if j + weights[i] <= W and dp[i-1][j]:
dp[i][j+weights[i]] = 1
pprint.pprint(dp)
for i in range(W,-1,-1):
if dp[-1][i]:
return i
if __name__ == '__main__':
max_weight = dp_bag(weights,W,n)
print(max_weight)
reference from 数据结构与算法之美 王争