By

Contents
  1. 1. 背包问题
  2. 2. 分析
  3. 3. 自底向上
    1. 3.1. 测试和输出
    2. 3.2. 分析
  4. 4. 带备忘的自顶向下
    1. 4.1. 对比测试与输出

上一节中对动态规划有了一个初步的认识，现在通过更多的例子来加深印象，在网上搜索了一下关于动态规划的经典问题，其中第一个就是所谓“背包问题”，事实上它也很类似上一节中的钢条切割，稍有不同。

背包问题

给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。

不同于上节钢条切割的地方是，物品的重量不是连续的，所以事先并不能知道任意物品组成的总重会的集合。

为了便于编程实现，将问题具体化，比如使用上一节中的数据，重量价格表P：

重量：  2    3    4    5    6    7    8    9    10
价值：  5    8    9   10   17   17   20   24    30

但是上一节中我们的输入不能>10，在背包问题中，没有这种限制。

分析

以r(n)表示最大重量为n时的最优解，p(i)为重为i的物品的价值，对问题进行分解：

r(n) = max[ p(i) + r(n-i) ]     #其中 i(min)<=i<=i(max)

如此问题的分解与结合就完成了, 需要注意的细节有

  1. n 或 n-i 不一定能通过组合得到
  2. 确保r(n)递增

自底向上

尝试使用bottom up的方式，从小到大求解最优解，直到满足问题的输入值n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bottom_up_bag(n, p):
    # make sure that records in mem is an optimal solution
    # init. { n: [ maxWeight, "combination"] }  
    mem = {0: [0, ""]}
    keys = p.keys()
    keys.sort()
    max = 0
    for sum in range(min(p.keys()), n + 1):
        for i in keys:
            if i > sum:
                break
            sub = sum - i
            if sub in mem:
                t = p[i] + mem[sub][0]
                if t > max and (sum not in mem or t > mem[sum][0]):
                    mem[sum] = [t, mem[sub][1] + str(i) + " "]
                    max = t
    return mem

测试和输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 测试代码
# 先用较少的物品，作便于分析
p = {3: 8, 5: 10}
r = bottom_up_bag(14,p)
for i in r:
    print i, r[i]
######以下为输出######
0 [0, '']
3 [8, '3 ']
5 [10, '5 ']
6 [16, '3 3 ']
8 [18, '5 3 ']
9 [24, '3 3 3 ']
11 [26, '5 3 3 ']
12 [32, '3 3 3 3 ']
14 [34, '5 3 3 3 ']

可以看到输出并不是连续的，4、7等是因为无法组合得到，而10是因为5+5组合价值为20,不及重量为9最优解24

这些不连续的值的最优解为与其相邻较小值的最优解，如背包容量为7时，最优解同容量6,为3+3；容量为10时，同容量9,取3+3+3

分析

算法的正确性是如何保证的？依然如前一节中所说，自底向上的算法的关键在于计算子问题时，确保更小的子问题已经求解。

初始条件为0：0，即重为0时价值为0；

最小子问题规模为最小单个物品重量，依次递增；

尝试所有可能的拆分：单个物品+子最优解（规模更小，一定已知），并取最大值（且要求较前一容量递增）

这种方法不是很严谨，因为无法预知可能组合成哪些数值，所以采用了++1这样的方式来试探，如果物品重量值很大，性能将非常低下

带备忘的自顶向下

这是更适合背包问题的解法，同样的分解思路，不过这次是自顶向下的递归调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def recurse_bag(n, p):
    # make sure that records in mem is an optimal solution
    mem = {0: [0, ""]}
    keys = p.keys()
    keys.sort()
    def inner(n, p):
        if n in mem:
            return mem[n]
        if n < min(keys):
            return [0,""]
        for i in keys:
            if i <= n:
                s = inner(n - i, p)
                t = p[i] + s[0]
                if n not in mem or t > mem[n][0]:
                    mem[n] = [t, "%s %s" % (s[1], str(i))]
            else:
                break
        return mem[n]
    inner(n,p)
    return mem

子问题一旦求解一次，就存储在备忘map中（变量mem），每次求解向查找备忘，无记录才求解，递归的另一个好处就是不必在意物品能组合成哪些数值。

对比测试与输出

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
p = {3: 8, 5: 10, 8: 20}
vol = 14
r1 = recurse_bag(vol, p)
r2 = bottom_up_bag(vol, p)
k1 = r1.keys()
k2 = r2.keys()
k1.sort()
k2.sort()
for i in range(max(len(k1), len(k2))):
    if i < len(k1):
        print k1[i], r1[k1[i]], "\t\t\t\t\t\t",
    if i < len(k2):
        print k2[i], r2[k2[i]],
    print ""

输出情况

1
2
3
4
5
6
7
8
9
0 [0, '']                       0 [0, ''] 
3 [8, ' 3']                         3 [8, ' 3'] 
4 [8, ' 3']                         5 [10, ' 5'] 
5 [10, ' 5']                        6 [16, ' 3 3'] 
6 [16, ' 3 3']                      8 [20, ' 8'] 
8 [20, ' 8']                        9 [24, ' 3 3 3'] 
9 [24, ' 3 3 3']                        11 [28, ' 8 3'] 
11 [28, ' 8 3']                         12 [32, ' 3 3 3 3'] 
14 [36, ' 8 3 3']                       14 [36, ' 8 3 3']

二者的记录的值并不一样，但对应的容量和最优解是一致的，递归比较能体现求解的过程，bottom up则列出了规模范围内所有的解。

Contents
  1. 1. 背包问题
  2. 2. 分析
  3. 3. 自底向上
    1. 3.1. 测试和输出
    2. 3.2. 分析
  4. 4. 带备忘的自顶向下
    1. 4.1. 对比测试与输出