Knapsack problem

Posted on | In | |
Different methods to solve 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