逐步解决动态规划之01背包问题

[站外图片上传中...(image-fe2902-1583294261806)]

什么是动态规划？

动态规划（Dynamic programming，简称DP），是一种通过“大而化小”的思路解决问题的算法。

动态规划没有明确的算法模板，准确的说，它是一种思想。动态规划是一种解决问题的思想。

什么样的题目适用于动态规划

1. 求最大值 / 最小值
2. 求可不可行
3. 求方案总数

以上三种问题基本上都是用动态规划来求解。

注意：如果问题是让你求出“所有的”方案和结果，则肯定不是使用动态规划。

动态规划问题的解决过程

主要以3个子目标来攻克此类问题：

1. 建立状态转移方程。
2. 缓存并复用以往结果。
3. 按顺序从小往大算。

举个简单的例子，1个人有2条腿，2个人有4条腿，...，100 个人有多少条腿？

首先要建立状态转移方程： f(n) = 2n

这个太简单了不用缓存复用，直接计算即可。

嘴上说还是不够的，我们用实际的问题从浅到深，逐步来深入了解动态规划问题。

[Talk is cheap. Show me the code]

一、斐波那契数列

• 斐波那契数列：0，1，1，2，3，5，8，13，21，34，55，89，144...

• 图形如下：

[图片上传失败...(image-cea13e-1583294261806)]

• 斐波那契数列规律计算公式如下：

[图片上传失败...(image-208a66-1583294261806)]

1. 先看看暴力递归方法：

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)


if __name__ == "__main__":
    result = fib(100)
    print(result) # 别等了 根本执行不出来

简单递归的时间复杂度达到了O(n²)。 因为每次都要进行重复计算。

f(3) = f(2) + f(1)

f(4) = f(3) + f(2)

可以看出，f(2) 计算了两次，计算的n越大，循环的次数越多。

2. 动态规划

   In [20]: def fib(n):
       ...:     result = list(range(n+1)) # 用于缓存以往结果，以便复用（目标2）
       ...:     for i in range(n + 1):   # 按顺序从小往大算（目标3）
       ...:         if i < 2:
       ...:             result[i] = i
       ...:         else:
                     # 使用状态转移方程（目标1），同时复用以往结果（目标2）
       ...:             result[i] = result[i - 1] + result[i - 2]
       ...:     return result[-1] # 输出列表中最后一个数值，也就是fib(n)的值
       ...:
   
   In [21]: result = fib(100)
   
   In [22]: result
   Out[22]: 354224848179261915075L
   

1. （目标1）状态转移方程是什么: f(n) = f(n-1) + f(n-2)
2. （目标2）缓存并复用以往的结果。在 result[i] = result[i - 1] +result[i - 2]中进行了复用。相当于你在计算了 + 1 + 1 + 1 + 1 + 1 + 1 + 1= 7 之后，再 + 1 你可以很快的计算出是 8 ，不必再重新将 8 个 1 相加。
3. （目标3）从小到大计算。这样以来，时间复杂度降为O(n)。我们只需要计算红圈圈出的部分即可。节省了大量的时间。

1583152807162.png

二、不同路径问题

参照LeetCode上的62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

上图是一个7 x 3 的网格。有多少可能的路径？

太多了，我简化一个3 X 2 的。

解这道题的时候，我们也要从三个目标开始

1. （目标1）状态转移方程是什么:

   这道题你必须要知道转移方程是什么。不然的话下面都不用做了...

   f(i, j) = f(i-1, j) + f(i, j - 1)

2. （目标2）缓存并复用以往的结果。这里是一个二维的行列问题。我在这里用二维的数组解决这个问题。

3. （目标3）同样也是从小到大计算。我们需要双重循环，逐行逐列进行计算。

# encoding:utf8
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int m为行数
        :type n: int n为列数
        :rtype: int
        """
        result = [[1] * n] * m
        for i in range(1, m):
            for j in range(1, n):
                result[i][j] = result[i][j - 1] + result[i - 1][j]
        return result[-1][-1]


if __name__ == '__main__':
    s = Solution()
    print s.uniquePaths(3, 7)

输出结果为28，证明我们的计算方法是正确的。

三、01背包问题

有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：eg：number＝4，capacity＝6

i（物品编号）	1	2	3	4
w（体积）	2	3	4	5
v（价值）	3	4	5	6

背包问题(0—1背包)

有N件物品，背包的最大承重为M，每件物品的数量均为1，价值集合为V，重量集合为W，计算该背包可以承载的物品的最大价值。
动态规划思想：

• 动态规划解题步骤：问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成

• 动态规划的原理：

  • 动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。
  • 但不同的是：
    • 分治法在子问题和子子问题等上被重复计算了很多次，
    • 而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

• 背包问题的解决过程
  在解决问题之前，为描述方便，首先定义一些变量：Vi表示第i个物品的价值，Wi表示第i个物品的体积，定义V(i,j)：当前背包容量j，前i个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中Xi 取0或1，表示第i 个物品选或不选）。

  此处要注意各个变量代表的含义，尤其是V(i,j)：当前背包容量j，前i个物品最佳组合对应的价值。

1、建立模型，即求max(V1X1+V2X2+…+VnXn)；

2、寻找约束条件，W1X1+W2X2+…+WnXn < capacity；

3、寻找递推关系式，面对当前商品有两种可能性：

图示：

	capacity		0	1	2	3	4	5	6
0	weight	value	0	0	0	0	0	0	0
1	2	3	0	0	3	3	3	3	3
2	3	4	0	0	3	4	4	7	7
3	4	5	0	0	3	4	5	7	8
4	5	6	0	0	3	4	5	7	8

# encoding:utf8
class Solution(object):
    def bag01(self, weights, values, capacity):
        # 动态规划
        n = len(weights)
        result = [[0 for j in range(capacity + 1)] for i in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, capacity + 1):
                result[i][j] = result[i - 1][j]
                # 背包总容量够放当前物体，遍历前一个状态考虑是否置换
                if j >= weights[i - 1] and result[i][j] < result[i - 1][j - weights[i - 1]] + values[i - 1]:
                    result[i][j] = result[i - 1][j - weights[i - 1]] + values[i - 1]
        for x in result:
            print(x)
        return result

    def show(self, weights, capacity, result):
        n = len(weights)
        print ('最大解为：{}'.format(result[n][capacity]))
        x = [False for i in range(n + 1)]
        j = capacity
        for i in range(n, 0, -1):
            if result[i][j] > result[i - 1][j]:
                # i代表第i个物品，如果放入第i个物品的价值大于同等重量放入i-1物品的重量，说明选择了物品i
                x[i] = True
                j -= weights[i - 1]
        print('items:')
        for i in range(n + 1):
            if x[i]:
                print('no:{}'.format(i))


if __name__ == '__main__':
    s = Solution()
    weights = [2, 2, 3, 1, 5, 2]
    values = [2, 3, 1, 5, 4, 3]
    capacity = 10
    result = s.bag01(weights, values, capacity)
    s.show(weights, capacity, result)

输出结果：

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[0, 0, 3, 3, 5, 5, 5, 5, 5, 5, 5]
[0, 0, 3, 3, 5, 5, 5, 6, 6, 6, 6]
[0, 5, 5, 8, 8, 10, 10, 10, 11, 11, 11]
[0, 5, 5, 8, 8, 10, 10, 10, 12, 12, 14]
[0, 5, 5, 8, 8, 11, 11, 13, 13, 13, 15]
最大解为：15
items:
no:2
no:4
no:5
no:6

Process finished with exit code 0

以上。