【crash DP】上下班路上学动态规划（2）

vlambda
2020-08-01

【crash DP】上下班路上学动态规划（2）

今天我们要学习的是背包问题，最经典的动态规划问题。建议你先看完再来看这篇文章，因为二者是一个连续的教程。本文会从暴力查找，自顶向下，自底向上三个角度来讲解，让你想不理解都不行！

问题描述

有N个物品，每个物品有重量和价值两个属性，还有一个承重为C的背包。现在让你用这个背包装物品，使所装物品的价值最大化。

举个具体点的例子，假设物品是水果，相关指标如下：水果种类：{苹果，橙子，香蕉，甜瓜}

重量：{2，3，1，4 }

价值：{4，5，3，7 }

背包容量：5

下面我们尝试在背包中放水果，同时确保它们的总重量不超过5：

苹果+橙（总重量5）=> 9价值
苹果+香蕉（总重量3）=> 7价值
橙+香蕉（总重量4）=> 8价值
香蕉+瓜（总重量5）=> 10价值

这表明香蕉+甜瓜是最好的组合，因为它给我们带来最大的价值，并且总重量不超过背包的承重量。

问题分析

复杂的问题也应该从简单的思路出发去分析。

对于这道题，一种基本的暴力解决方案是尝试给定项目的所有组合（如上所述），从中找出价值最高且重量不超过C的项目。以四个物品（A，B，C和D）为例，如下图所示。要尝试所有组合，我们的算法将如下所示：

for 每个物品 i：
  如果总重量不超过C，则创建一个包含物品i的集合，然后在剩余的物品和承重量上递归调用该方法
  创建一个不包含物品i的集合，然后在剩余的物品和承重量上递归调用该方法
返回 上述集合中价值最高的集合

在上面的图中，所有绿色的集合都是满足背包承重要求的（本例中是7）。所有红色的集合都是超重的集合。最佳的选项是[B,D]，总价值是22，总重量恰好为7。

用python实现的暴力算法如下所示：

def solve_knapsack(profits, weights, capacity):
  return knapsack_recursive(profits, weights, capacity, 0)


def knapsack_recursive(profits, weights, capacity, currentIndex):
  # 边界检查
  if capacity <= 0 or currentIndex >= len(profits):
    return 0

  # 如果当前访问的物品重量没有超出剩余的承重量，则将该物品放入背包后，在剩余的物品和剩余的承重量上递归调用
  profit1 = 0
  if weights[currentIndex] <= capacity:
    profit1 = profits[currentIndex] + knapsack_recursive(
      profits, weights, capacity - weights[currentIndex], currentIndex + 1)

  # 不将当前物品放入背包，在剩余物品和承重量上递归调用
  profit2 = knapsack_recursive(profits, weights, capacity, currentIndex + 1)
  # 返回上述两种方案中价值最大的方案
  return max(profit1, profit2)

上面的暴力搜索算法的时间复杂度是。这个我们可以从上面的例子中看出来，有4个物品时，递归调用的次数是31次，即。

空间复杂度是。这部分空间主要是用来存储我们的调用栈，因为一共n个节点，我们使用的又是深度优先遍历算法，所以最深的递归调用长度也不可能超过n。

自顶向下加记忆

这个暴力算法时间复杂度可以说是相当的高，我们怎么优化呢？既然是讲动态规划，我们自然是想用动态规划来解决。要用动态规划，我们首先需要的就是看看暴力搜索算法中有没有重叠的子问题。

不难发现，在我们的递归调用方法中，profits和weights两个数组是保持不变的，变化的是当前剩余承重量和当前元素位置，我们分别用c和i来表示。

现在，我们可以将上面的递归调用过程重新改写成下面这样：

这一下，我们就可以清楚地看到，“c:4,i=3”这个子问题被计算了两次，也就是说存在重叠的子问题，按照（1）中所讲，我们可以用自顶向下加记忆或者自下而上加表格的方法来优化重叠的子问题。

所谓记忆，就是当我们求解出一个子问题的解时，将其缓存起来，当需要再次求解时，直接从缓存中提取结果，不再需要重新计算了。

具体如何缓存呢？分析一下我们的递归调用，因为只有承重量capacity和当前物品currentIndex是变化的，这提示我们，可以用一个二维数组来存储子问题的解。

具体代码如下所示：


def solve_knapsack(profits, weights, capacity):
  # 创建一个二维数组缓存子问题的解，初始化为-1
  dp = [[-1 for x in range(capacity+1)] for y in range(len(profits))]
  return knapsack_recursive(dp, profits, weights, capacity, 0)


def knapsack_recursive(dp, profits, weights, capacity, currentIndex):

  # 边界检测
  if capacity <= 0 or currentIndex >= len(profits):
    return 0

  # 命中缓存，直接从缓存中返回结果
  if dp[currentIndex][capacity] != -1:
    return dp[currentIndex][capacity]

  # 包含当前物品后，递归调用
  profit1 = 0
  if weights[currentIndex] <= capacity:
    profit1 = profits[currentIndex] + knapsack_recursive(
      dp, profits, weights, capacity - weights[currentIndex], currentIndex + 1)

  # 排除当前物品后，递归调用
  profit2 = knapsack_recursive(
    dp, profits, weights, capacity, currentIndex + 1)

  dp[currentIndex][capacity] = max(profit1, profit2)
  return dp[currentIndex][capacity]

该算法的时间复杂度如何呢？因为我们已经通过二维数组将子问题的解进行了缓存，所以我们最多需要计算的子问题的次数不会超过，N是物品数量，C是背包承重量。所以，该算法的时间复杂度是：。

空间复杂度呢？显然，为了缓存子问题的结果，我们需要的二维数组的空间。除此之外，还需要加上递归调用栈需要的的空间，二者相加，空间复杂度大约就等于了。

自底向上加表格

使用自底向上的方法，我们仍然是要填充和上面的解法相同的二维数组dp[][]。只不过这一次，我们需要格外强调一个事实，就是dp[i][c]的意义，它实际上指的是，当承重量是c时，使用前i个物品进行装填，所能得到的最大价值。

基于这个意义，我们发现dp[i][c]的值实际上可以分解成如下两种可能：

不包含当前物品i。这种情况下，和 dp[i-1][c]相同
包含当前物品i。这时要求物品i的重量不超过剩余承重量c。此时，最大价值等于当前物品i的价值，再加上剩余物品和剩余承重量的最大可能价值。即：profit[i] + dp[i-1][c-weight[i]]

综上，我们最后的最优解，就是上面两种可能的最大值：

dp[i][c] = max (dp[i-1][c], profit[i] + dp[i-1][c-weight[i]])

下面，我们从图形的角度来理解一下整个数组填充的过程：

当承重量为0时，不管有多少物品可供选择，最大的可能价值都是0。

当承重量从1增加到7，只有一个物品时，当该物品的重量不大于承重量时，就应该将它放入背包，且该物品的价值就是最优解。

当承重量为1，物品数量为2时，因为第2个物品的重量是2，超过了此时的承重量1，所以此时的最优解就是dp[index-1][capacity]。

当承重量为2，物品数量为2时，从上面讨论的公式可以知道：

max(dp[0][2], profit[1] + dp[0][0])

当承重量为3，物品数量为2时，类似上面可以得到：

max(dp[0][3], profit[1] + dp[0][1])

按照这个规则一直填充下去，我们最终会得到如下的表格：

最右下角的元素，就是我们的答案22！

代码实现如下：

def solve_knapsack(profits, weights, capacity):
  # 边界检测
  n = len(profits)
  if capacity <= 0 or n == 0 or len(weights) != n:
    return 0

  # 全部初始化为0
  dp = [[0 for x in range(capacity+1)] for y in range(n)]

  # 填充承重量为0时，即表格中的第1列
  for i in range(0, n):
    dp[i][0] = 0

  # 填充只有一个物品时，即表格中的第1行
  for c in range(0, capacity+1):
    if weights[0] <= c:
      dp[0][c] = profits[0]

  # 两个for循环用来填充整个数组
  for i in range(1, n):
    for c in range(1, capacity+1):
      profit1, profit2 = 0, 0
      # 当前物品i小于承重量c时，包含它
      if weights[i] <= c:
        profit1 = profits[i] + dp[i - 1][c - weights[i]]
      # 不包含当前物品i
      profit2 = dp[i - 1][c]
      # 取最大值
      dp[i][c] = max(profit1, profit2)

  # 返回整个问题的最优解
  return dp[n - 1][capacity]

虽然求出了最优解，但还是有一个问题，如何找出最优解时放入背包中的物品呢？

这时，我们需要一个逆向思维，从得到的最优解出发，一步步去倒求这个最优解是如何得到的。根据我们上面的求解过程，我们不难发现：

当dp[i][c] == dp[i-1][c]时，说明最优解中是不包含当前物品i的，如果二者不相等，则说明最优解中是包含了当前物品i。

据此，我们就可以找出最优解中放入背包的物品啦！

代码实现如下：

def print_selected_elements(dp, weights, profits, capacity):
  print("Selected weights are: ", end='')
  n = len(weights)
  totalProfit = dp[n-1][capacity]
  for i in range(n-1, 0, -1):
    if totalProfit != dp[i - 1][capacity]:
      print(str(weights[i]) + " ", end='')
      capacity -= weights[i]
      totalProfit -= profits[i]

  if totalProfit != 0:
    print(str(weights[0]) + " ", end='')
  print()

往期精彩回顾

vlambda博客
学习文章列表