Knapsack problem

Backtracking

我们把物体依次排列,整个问题就分为n个阶段,每个阶段对应一个物品 i 怎样选择。

bag.jpg
观察解空间树,每个结点我们用(i,cw)来表示。i表示将要觉得i个物品是否装入背包,只有装和不装两种情况。cw 表示当前背包中的重量。比如(2,2)表示我们将要觉得第2个物品是否装入背包,在决策前,背包中物品的总重量是2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
weights = [2,2,4,6,3]
W = 9
n = 5

max_weight = 0

def backtracking_bag(i, cw, items):
global max_weight,methods
"""
i: test the item i
cw: current total weight
weights: the weight of items
W: total weight the bag can load
n: the number of items
max_weight: the max weight the bag can load
"""
if i == n:
if cw <= W and cw >= max_weight:
if cw > max_weight:
max_weight = cw
methods = []
methods.append(items[:])
else:
methods.append(items[:])
return

backtracking_bag(i+1,cw,items)

if cw + weights[i] <= W:
items[i] = 1
backtracking_bag(i+1,cw+weights[i],items)
items[i] = 0



if __name__ == '__main__':
items = [0] * n
methods = []
backtracking_bag(0,0,items)
print(max_weight)
print(methods)

Backtracking with memory

我们发现,很多子问题是重复的。比如f(2,2) 和 f(3,6)都被重复计算很多次。因此,我们可以用备忘录的方法来解决重复计算的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
weights = [2,2,4,6,3]
W = 9
n = 5

max_weight = 0

def backtracking_memory_bag(i, cw, items):
global max_weight,methods,memory
"""
i: test the item i
cw: current total weight
weights: the weight of items
W: total weight the bag can load
n: the number of items
max_weight: the max weight the bag can load
"""
if i == n:
if cw <= W and cw >= max_weight:
if cw > max_weight:
max_weight = cw
methods = []
methods.append(items[:])
else:
methods.append(items[:])
return

if memory[i][cw]:
return
memory[i][cw] = True # remember the state of i

backtracking_bag(i+1,cw,items)
if cw + weights[i] <= W:
items[i] = 1
backtracking_bag(i+1,cw+weights[i],items)
items[i] = 0

if __name__ == '__main__':

items = [0] * n
methods = []
memory = [[False]*W for i in range(n)]
backtracking_bag(0,0,items)
print(max_weight)
print(methods)

Dynamic Programming

我们把整个求解的过程分为n个阶段,每个阶段会决策一个物品是否放入背包中。每个物品决策完成后,背包中的重量会有多种情况。
动态规划问题的解决步骤一般可以总结为 3 步:

  1. 定义数组元素的含义
    我们用 dp[n][cw] 来表示在第n个阶段重量为cw的状态。
  2. 找出状态转移方程。
    • 把第 i 个物品装入背包中
    • 不把第 i 个物品装入背包中比如第 0 个物品的重量是2,要么装入背包,要么不装入背包。决策完之后会对应背包的两种状态,背包中物品的总重量为 0 或者 2。
      我们用dp[0][0] = true 和 dp[0][2] = true表示。

  3. 初始值。
  • 第 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 数据结构与算法之美 王争

Donate article here