动态规划-背包问题（上接递归）

[TOC]

动态规划：

  • 动态规划算法采用了一种更有条理的方式来得到问题的解
  • 找零兑换的动态规划算法从最简单的“1分钱找零”的最优解开始， 逐步递加上去， 直到我们需要的找零钱数
  • 在找零递加的过程中， 设法保持每一分钱的递加都是最优解， 一直加到求解找零钱数， 自然得到最优解
  • 递加的过程能保持最优解的关键是， 其依赖于更少钱数最优解的简单计算， 而更少钱数的最优解已经得到了。
  • 问题的最优解包含了更小规模子问题的最优解， 这是一个最优化问题能够用动态规划策略解决的必要条件

博物馆大盗问题

大盗潜入博物馆， 面前有5件宝物， 分别有重量和价值， 大盗的背包仅能负重20公斤， 请问如何选择宝物， 总价值最高？

item weight value
1 2 3
2 3 4
3 4 8
4 5 8
5 9 10

我们把$m(i, W$记为：
前$i(1<=i<=5)$个宝物中，组合不超过$W(1<=W<=20)$ 重量，得到的最大价值$m(i, W)$应该是$m(i-1, W)$和$m(i-1, W-W_i)+v_i$两者最大值
我们从$m(1, 1)$开始计算到$m(5, 20) $

博物馆大盗问题：动态规划表格

m 0 1 2 3 4 5 …
0 0 0 0 0 0 0
1 0 0 3 3 3 3
2 0 0 3 4 4 7
3 0 0 3 4 8 8
4 0 0 3 4 8 8
5 0 0 3 4 8 8 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 宝物的重量和价值
tr = [None, {'w':2, 'v':3},{'w':3, 'v':4},{'w':4, 'v':8},
      {'w':5, 'v':8},{'w':9, 'v':10}]
# 大盗最大承重
max_w = 20
# 初始化二维表格m[(i, w)]
# 表示前i个宝物中，最大重量w的组合，所得到的最大价值
# 当i 什么都不取，或w上线为0，价值为0
m = {(i, w): 0 for i in range(len(tr)) for w in range(max_w+1)}
# 逐个填写表格
for i in range(1, len(tr)):
    for w in range(1, max_w+1):
        if tr[i]['w'] > w: # 装不下第i个宝物
            m[(i, w)] = m[(i-1, w)]  # 不装第 i 个宝物
        else:
            # 装第 i 个宝物,不装第 i 个宝物,两种情况下的最大值
            m[(i, w)] = max(m[(i-1, w)], m[(i-1, w-tr[i]['w'])]+tr[i]['v'])
# 输出结果
print(m[(len(tr)-1, max_w)])

递归求解：

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
# 宝物的重量和价值
tr = {(2, 3), (3, 4), (4, 8), (5, 8), (9, 10)}
# 大盗最大承重
max_w = 20
m = {}


def thief(tr, w):
    
    if tr == set() or w == 0:
        m[(tuple(tr),w)] = 0
        return 0
    elif (tuple(tr),w) in m:
        return m[(tuple(tr), w)]
    else:
        vmax = 0
        for t in tr:
            if t[0] <= w:
                v = thief(tr-{t}, w-t[0]) + t[1]
                vmax = max(vmax, v)
        m[(tuple(tr), w)] = vmax
        return vmax


print(thief(tr, max_w))