【引言】有一个准备偷东西的小偷，他有一个用来偷东西的背包，这个背包只能装4斤重的东西。但是他所要偷的店里，却有几十种上百种的商品，这些商品质量价格不一，那么他该如何选择才能偷到最好的一个物品集合使得他所偷取的东西总价最高呢？

动态规划也是一种能将问题的规模缩小，解决了小问题，逐渐的扩大问题规模就最终得到了问题的解答的这么一个算法。

算法过程

背包问题

如引言里所说，小偷偷东西的这种问题，就是背包问题。背包问题需要我们选择出最好的一个物品组合来实现小偷偷东西的利益最大化。

问题规模

实际上，我们仔细思考这个问题的时候，可能脑海里第一个出来的方案就是把所有能偷的组合都列举出来，我们选择其中背包能装下的并且所偷物品价值最高的一个不就得了。但是，这样做的代价是很高的。

对于小偷所要想偷的东西，有N种，这N种就是一个可供选择的集合，小偷需要从中选择一个子集来偷，含有N个元素的集合的子集的个数是：

含有N个元素的集合的子集个数.png

动态规划

我们跟着动态规划算法的过程来看一下，动态规划是怎么“动态”的规划小偷该偷哪几种东西。简单一点，我们现在的问题变为，小偷的背包只能装4斤重的东西，他可以偷的东西只有三种分别是：

小偷可以偷的东西列表.png

此时背包容量只有4，要想拿走所有的东西，背包是装不下的，所以要有所取舍。我们使用动态规划来进行操作。所有商品的质量（为了简便）都是整数，背包容量是4，我们就用所有商品质量中的最小的分割单位(1斤)来对背包的容量进行分割，形成一个以最小单位为列(背包容量是最大值)，每件商品为行的一个表格：

建立分别以质量最小划分单位和商品信息为横纵坐标的表格.png

接下来，我们开始填充表格，在整个填充过程完成之后，我们就能得到最终的选择结果了。

我们从上至下，从左至右的填充整个表格。首先来看第一排，第一排的意思是，小偷此时 只能选择偷取Bose耳机 ，小偷背包的最大容量是4，我们拆分开来，假如我们分别拿出1、2、3、4(最大)的容量来偷取Bose耳机，我们把每种容量偷取Bose耳机所能获取的偷取商品的最大价值填入表格。

由于Bose耳机的质量是1，所以，当背包容量是1的时候，小偷是可以偷取Bose耳机的，所以第一个格子我们填入Bose的价格3000：

第一个格子填充完毕.png

继续向后填写。第二个格子，此时背包容量是2，但是小偷现在只能偷取Bose耳机，尽管Bose耳机的质量是1不能够填满背包。所以第二个格子还是只能装一个Bose耳机，同理背包容量是3、4此时在第一行都只能填入一个Bose耳机，于是我们就将表格的第一排都填充完毕了：

第一排填充完毕.png

此时，图表告诉我们的是，如果我只能偷取Bose耳机这一种东西的话，当背包容量为4的时候，我最多能偷取的物品的价值就是3000(一个Bose耳机)

继续向下走，我们开始填充第二排，第二排代表的是，此时，小偷不仅能偷取Bose耳机，还能够偷取iPhone，而且小偷要优先于iPone偷取 。

首先是第二排的第一个位置，此时背包容量是1。我们通过第一排知道，目前为止，当背包容量为1的时候，小偷所能偷取的最大的价值是3000。此时，因为iPhone的质量是3，装不下，所以此时所能偷取的物品的最大价值还是3000：

第二行第一个格子填充完毕.png

此时来到了第三个格子，这个格子代表此时背包的容量为3，正好可以装下iPhone。如果小偷此时装下iPhone，那么这个格子的价值将是8000，比之前(上一行容量3的位置)的3000要高，所以小偷此时偷取的物品变为iPhone，价值变为8000:

所能偷取的最大价值发生变化.png

到了第二排第四个格子，此时背包容量为4，小偷可以先装入iPhone，装入了iPhone之后，背包容量被占用了3，还剩下1。此时小偷偷取了iPhone之后剩下的这1的容量还能装入的最大价值的物品是哪些呢？这个答案要从第一排来找，因为第一排是除了iPhone之外剩下小偷所能偷的所有的商品的所对应的不同容量下的最大价值。这时我们找到了，当容量为1(第二排的4容量装了3容量的iPhone之后所剩下的)时，小偷能装入背包的最大的价值就是第一排的第一个格子所记录的3000！：

第二排最后一个格子.png

此时，当小偷手中只有一个容量为4的背包时，所能偷取的最大的物品的价值是11000。

最后一排。来到最后一排，这时，小偷能偷取的物品又多了一个iPad 。

最后一排第一个格子，当背包容量为1的时候。由于iPad的质量为4装不下，所以，我们还是看它上一排，除了iPad之外所能装在容量为1的背包中的最大的价值，是3000，同理最后一排第二个跟第三个格子也是如此：

第四排前三个格子填充完毕.png

我们来到了最后一排的最后一个格子。此时背包容量为4，iPad的质量也为4，iPad的价格是10000。当小偷背包中不放iPad的时候(上一行的容量4的位置)，容量为4的背包所能装的最大的商品价值是上一排代表容量为4的格子所填写的11000。11000 > 10000。也就是说如果背包此时不装iPad，改装除了iPad之外其他的东西，所能装的最大的价值要比装iPad要高。那么小偷就不装iPad，继续延续之前的选择的物品：

表格填充完毕.png

至此，表格填充完毕。最后一个格子所代表的含义就是，当小偷可以选择的商品有 Bose耳机、iPhone、iPad与此同时背包容量为4的情况下，所能偷取的商品是Bose耳机、iPhone，总价值是11000。

回顾一下最终的做出选择的流程，我们总结一下规律：

整体流程.png

对于每个格子，填入格子中的值不外乎是这两种中的一种：

格子中的值有两种情况.png

既然保证利益最大化，我们就取这两种赋值方式中能得到的值较大的那个。这样，我们整体的动态规划的流程就结束了。

动态规划是将整个一个大问题零敲碎打，分解成为背包容量分别为1、2、3、4时候，物品分别为：Bose耳机；Bose耳机、iPhone；Bose耳机、iPhone、iPad这样依次增加商品的情况下最终通过解决每个小格子，来使最终的这个大的格子所代表的问题得到解决。这样做的好处在于如果我们此时再增加一个商品，无非就是再多出一行来计算，最终也可以得到正确的结果！回顾一开始的假设，加入有100种商品，动态规划所需要的计算步骤需要 4 × 100 = 400 < 1267650600228229401496703205376 ，非常可观。

算法实现

# -*- coding: utf-8 -*-
# @Time    : 2019-03-19 09:17
# @Author  : Jaedong
# @Version : 3.6
# @File    : DynamicProgramming.py
# @Software: PyCharm

class Goods:
    name = ''
    price = 0
    weight = 0

    def __init__(self, name, price, weight):
        self.name = name
        self.price = price
        self.weight = weight


def dynamic_programming(goods, min, max, step):
    # 初始化分部计算的中间过程
    steps = [[0 for col in range(min, max + 1, step)] for raw in range(len(goods))]
    choosed = []
    # 每一行的每一个格子(分开的步骤)
    for i in range(len(goods)):
        # 每一列的每一个格子(分开的步骤)
        for j in range(min - step, max, step):
            weight = goods[i].weight # 拿到当前行的物品的重量
            sameWeightMax = 0 # 初始化相同重量(同一列)上面已知的不包括本物品(本行物品)的最大的重量所装物品的价值
            currentStepPrice = goods[i].price # 当前一行不同重量所能装的最多物品的价值

            # 为了防止越界，第一行要特殊处理，非第一行的才走下面的赋值逻辑，其实也可以用哨兵
            if i != 0:
                sameWeightMax = steps[i - 1][j]

                if j >= weight:
                    currentStepPrice = steps[i - 1][j - weight] + currentStepPrice

            # 如果商品的重量小于等于背包的可以承受的重量，那么就可以考虑是否应该装进去， j+step是当前步骤的重量
            if weight <= j + step:
                if sameWeightMax > currentStepPrice:
                    steps[i][j] = sameWeightMax
                else:
                    steps[i][j] = currentStepPrice
            else:
                steps[i][j] = sameWeightMax

    # 回溯一下，找到所包含的物品都有什么
    choosed = []
    colIndex = max - 1 # 减1之后代表的是下标，不减1代表重量
    for i in range(len(goods) - 1, -1, -1):
        good = goods[i]
        if steps[i][colIndex] > steps[i-1][colIndex]:
            choosed.append(goods[i].name)
            colIndex = colIndex - good.weight

    if colIndex >= 0: # 如果最终还有重量在的话（真实重量应该+1），这里避免了首个商品恰好是漏下没有记录的情况
        choosed.append(goods[0].name)

    return choosed


goods = [
    Goods('Bose耳机', 3000, 1),
    Goods('iPhone', 8000, 3),
    Goods('MacBook Pro', 10000, 4)
]

# 这个示例是以重量为整数单位，如果涉及到小数，可以适当的进行改版
choosed = dynamic_programming(goods, 1, 4, 1)
print('最终选择的商品是：{}'.format(choosed))

结果是：

算法的最终结果.png

上一篇：写给媳妇儿的算法（十三）——贝尔曼-福德算法
下一篇：写给媳妇儿的算法（十五）——二叉树及其遍历