zdaiot

404NotFound

39初识动态规划：如何巧妙解决“双十一”购物时的凑单问题

发表于 分类于
本文字数： 10k 阅读时长 ≈ 9 分钟

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

双十一有很多促销活动，比如“满200元减50元”。假如购物车有 n 个（n>100）商品，要从中选几个，在凑够满减条件前提下，让选出的商品价格总和最大程度地接近满减条件（200）元。这怎么使用代码解决呢？这就需要用到今天讲到的动态规划（Dynamic Programming）。

动态规划学习路线

动态规划比较适合来求解最优问题，比如求最大值、最小值等。它可以显著降低时间复杂度，提高代码执行效率。不过，跟递归类似，它求解问题的过程不太符合人类常规的思维方式。

这次，主要分为三节来讲解：

  1. 初识动态规划：使用两个非常经典的动态规划问题模型，展示为什么要动态规划、动态规划问题解题方法是如何演化出来的。其它很多动态规划问题，都可以套用类似的思路来解决。
  2. 动态规划理论：总结动态规划适合解决的问题的特征，以及动态规划解题思路。另外，还将贪心、分治、回溯、动态规划这四种算法放在一起，对比分析它们各自的特点以及适用的场景。
  3. 动态规划实战：根据第二节讲的动态规划理论知识，实战解决三个非常经典的动态规划问题，加深你对理论的理解。

0-1 背包问题

从一组不同重量、不可分割的物品中选择一些装入背包，在满足背包最大重量前提下，背包中物品总重量的最大值是多少？

上一节使用了回溯的解决方法，也就是穷举搜索所有可能的装法，找到满足条件的最大值。但是回溯算法的复杂度很高，是指数级别的。那能不能借助规律，有效降低时间复杂度呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 回溯算法实现。注意：我把输入的变量都定义成了成员变量。
private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2，2，4，6，3};  // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
public void f(int i, int cw) { // 调用f(0, 0)
  if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
    if (cw > maxW) maxW = cw;
    return;
  }
  f(i+1, cw); // 选择不装第i个物品
  if (cw + weight[i] <= w) {
    f(i+1,cw + weight[i]); // 选择装第i个物品
  }
}

画图如下，假设背包的最大承载重量是 9。有5个重量分别为2,2,4,6,3的不同物品。把这个例子的回溯求解过程用递归树画出来，如下所示：

img

递归树中每个节点表示一种状态，用（i, cw）表示。其中 i 表示将要决策第几个物品是否装入背包，cw 表示当前背包中物品的总重量。比如（2，2）表示我们将要决策第 2 个物品是否装入背包，在决策后，背包中物品的总重量是 2。

从递归树中，发现有些子问题的求解是重复的。比如图中 f(2, 2) 和 f(3,4) 都被重复计算了两次，这两次重复计算体现在下面的递归树分支相同。借助递归小节讲过的“备忘录”解决方法，记录已经计算好的 f(i, cw)，当再次计算到重复的 f(i, cw) 的时候，可以直接从备忘录中取出来用，就不用再递归计算了，这样就可以避免冗余计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2，2，4，6，3};  // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
// 备忘录，默认值false；以为还有重量为0的，所以数组第二维度最大为10，而不是9
private boolean[][] mem = new boolean[5][10]; 
public void f(int i, int cw) { // 调用f(0, 0)
  // cw==w表示装满了，i==n表示物品都考察完了。下面代码已经排除过 cw>w 的情况了
  if (cw == w || i == n) { 
    if (cw > maxW) maxW = cw;
    return;
  }
  if (mem[i][cw]) return; // 重复状态，这种情况只需要计算一遍
  mem[i][cw] = true; // 记录(i, cw)这个状态已经遍历过了
  f(i+1, cw); // 选择不装第i个物品
  if (cw + weight[i] <= w) {
    f(i+1,cw + weight[i]); // 选择装第i个物品
  }
}

实际上，它已经跟动态规划的执行效率相差不大了。现在看看动态规划是怎么做的？

把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策（放入或者不放入）完之后，背包里的物品质量会有很多种情况。对应到递归树中，就是有很多不同的节点。

观察上面的递归树图，可以把每一层中重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。可以通过合并每一层重复的状态，保证每一层不同状态的个数都不会超过 w 个（w 表示背包的承载重量），也就是例子中的 9。避免每层状态个数的指数级增长。可以用一个二维数组 states[n][w+1]，记录每层可以达到的不同状态。因为含有重量为0的情况，所以二维数组第二维的大小为 w+1，而不是w。

第0个（下标从0开始编号）物品的重量是2，决策完装与不装之后，对应背包的两种状态，背包中物品的总重量为0或者2。用states[0][0]=true 和 states[0][2]=true 来表示这两种状态；第1个物品的重量也是2，基于之前背包的状态，这个物品决策完之后，不同的状态有 3 个，背包中物品总重量分别是 0(0+0)，2(0+2 or 2+0)，4(2+2)。可以用states[1][0]=true，states[1][2]=true，states[1][4]=true 来表示这三种状态。

依次类推，直到考察完所有的物品，整个 states 状态数组就都计算好了。整个计算过程如下所示。其中 0 表示 false，1表示 true。我们只需在最后一层，找到一个值为 true的最接近 w （这里为9）的值，就是背包中物品总重量的最大值。

img

img

对应的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
weight:物品重量，n:物品个数，w:背包可承载重量
public int knapsack(int[] weight, int n, int w) {
  boolean[][] states = new boolean[n][w+1]; // 默认值false
  states[0][0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
  if (weight[0] <= w) {
    states[0][weight[0]] = true;
  }
  for (int i = 1; i < n; ++i) { // 动态规划状态转移
    for (int j = 0; j <= w; ++j) {// 不把第i个物品放入背包
      if (states[i-1][j] == true) states[i][j] = states[i-1][j];
    }
    for (int j = 0; j <= w-weight[i]; ++j) {//把第i个物品放入背包
      if (states[i-1][j] == true) states[i][j+weight[i]] = true;
      // 当不满足这个if条件时，说明没有这条途径到达这里
    }
  }
  for (int i = w; i >= 0; --i) { // 输出结果
    if (states[n-1][i] == true) return i;
  }
  return 0;
}

实际上， 这就是一种用动态规划解决问题的思路。把问题分解为很多个阶段，每个节点对应一个决策。记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。这就是动态规划名词的由来。

回溯算法解决这个问题的时间复杂度为$O(2^n)$，为指数级别。而动态规划解决这个问题。耗时最多的就是代码中的两层for循环，时间复杂度为$O(n*w)$。n 表示物品个数，w 表示背包可以承载的总重量。

尽管动态规划的执行效率比较高，但是需要额外申请一个 n 乘以 w+1 的二维数组，对空间的消耗比较多。所以有时也说，动态规划是一种拿空间换时间的解决思路。那如何讲的空间消耗呢？实际上，可以用一个大小为 w+1 的一维数组解决这个问题。动态规划状态转移的过程，都可以基于这个一维数组来操作。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int knapsack2(int[] items, int n, int w) {
  boolean[] states = new boolean[w+1]; // 默认值false
  states[0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
  if (items[0] <= w) {
    states[items[0]] = true;
  }
  for (int i = 1; i < n; ++i) { // 动态规划
    for (int j = w-items[i]; j >= 0; --j) {//把第i个物品放入背包
      // 下面if条件成立，说明有路径可以到达这里
      if (states[j]==true) states[j+items[i]] = true;
    }
  }
  for (int i = w; i >= 0; --i) { // 输出结果
    if (states[i] == true) return i;
  }
  return 0;
}

这里特别强调一下代码中的第 8 行，j 需要从大到小来处理。如果我们按照 j 从小到大处理的话，会出现 for 循环重复计算的问题。

0-1 背包问题升级版

之前的背包问题，只涉及背包重量和物品重量。现在引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品，在满足背包最大重量限制的前提下，如何挑选物品装入背包，使得背包中可装入物品的总价值最大。

这个同样可以用回溯算法解决，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private int maxV = Integer.MIN_VALUE; // 结果放到maxV中
private int[] items = {2，2，4，6，3};  // 物品的重量
private int[] value = {3，4，8，9，6}; // 物品的价值
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
public void f(int i, int cw, int cv) { // 调用f(0, 0, 0)
  if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
    if (cv > maxV) maxV = cv;
    return;
  }
  f(i+1, cw, cv); // 选择不装第i个物品
  if (cw + weight[i] <= w) {
    f(i+1,cw+weight[i], cv+value[i]); // 选择装第i个物品
  }
}

针对代码，画出递归树。在递归树中，每个节点表示一个状态。现在需要使用三个变量（i, cw, cv）来表示一个状态。其中 i 表示决策第 i 个物品是否装入背包，cw 表示当前背包中物品的总重量，cv 表示当前背包中物品的总价值。

img

类似于之前的背包问题，有几个节点的 i 和 cw 是完全相同的。比如 f(2,2,4) 和 f(2,2,3)。而在背包中物品总重量一样的情况下，f(2,2,4) 这种状态对应的物品总价值更大，所以可以舍弃 f(2,2,3) 这种状态，继续沿着 f(2,2,4) 这条决策路线继续往下决策即可。也就是对于 (i, cw) 相同的不同状态，只需要保留 cv 值最大的那个，继续递归处理，其他状态不予考虑。

如果这个思路使用回溯算法实现，就没法再用“备忘录”解决了。所以可以尝试一下动态规划方法。将整个分解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个阶段决策完之后，背包中的物品的总重量以及总价值，会有多种情况，也就是会达到多种不同的状态。

使用一个二维数组 states[n][w+1] 来记录每层可以达到的不同状态。不过该数组中存储的不再是 boolean 类型的了，而是当前状态对应的最大总价值。把每一层中 (i, cw) 重复的状态（节点）合并，只记录 cv 值最大的那个状态，然后基于这些状态来推导下一层的状态。对应的代码如下：

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
26
27
28
29
30
31
32
33
public static int knapsack3(int[] weight, int[] value, int n, int w) {
  int[][] states = new int[n][w+1];
  for (int i = 0; i < n; ++i) { // 初始化states
    for (int j = 0; j < w+1; ++j) {
      states[i][j] = -1;
    }
  }
  states[0][0] = 0;  // 第一行的数据要特殊处理，可以利用哨兵优化
  if (weight[0] <= w) {
    states[0][weight[0]] = value[0];
  }
  for (int i = 1; i < n; ++i) { //动态规划，状态转移
    for (int j = 0; j <= w; ++j) { // 不选择第i个物品
      if (states[i-1][j] >= 0) states[i][j] = states[i-1][j];
    }
    for (int j = 0; j <= w-weight[i]; ++j) { // 选择第i个物品
      // 若不大于0，则没有途径来到这步骤
      if (states[i-1][j] >= 0) {
        int v = states[i-1][j] + value[i];
        // 只记录 cv 值最大的那个状态
        if (v > states[i][j+weight[i]]) {
          states[i][j+weight[i]] = v;
        }
      }
    }
  }
  // 找出最大值
  int maxvalue = -1;
  for (int j = 0; j <= w; ++j) {
    if (states[n-1][j] > maxvalue) maxvalue = states[n-1][j];
  }
  return maxvalue;
}

跟上一个例子相同，这个例子的时间复杂度为$O(nw)$，空间复杂度为$O(nw)$。同样，这个时间复杂度是可以优化的。

解答开篇

对于这个问题，可以采用回溯算法，穷举所有可能的排列组合，看大于等于 200 并且最接近 200 的组合是哪一个？但是时间复杂度很高，是成指数级形式的。

实际上，它跟第一个例子中讲的 0-1 背包问题很像，只不过是把“重量”换成了“价格”而已。针对购物车中的 n 个商品中的每一个，均可以决策是否购买。每次决策之后，对应不同的状态集合。我们还是用一个二维数组 states[n][x]，来记录每次决策之后所有可达的状态。0-1 背包问题中，找的是小于等于 w 的最大值，x 就是背包的最大承载重量 w+1。对于本问题，要寻找的是大于等200的值中最小的，同时也不能超过200太多了，所以可以限定 x 值为1001。同样的，对于这个问题，还要会利用 states 数组，倒推出这个最小总价格对应都要购买哪些商品。对应的代码如下：

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
26
27
28
29
// items商品价格，n商品个数, w表示满减条件，比如200
public static void double11advance(int[] items, int n, int w) {
  boolean[][] states = new boolean[n][3*w+1];//超过3倍就没有薅羊毛的价值了
  states[0][0] = true;  // 第一行的数据要特殊处理
  if (items[0] <= 3*w) {
    states[0][items[0]] = true;
  }
  for (int i = 1; i < n; ++i) { // 动态规划
    for (int j = 0; j <= 3*w; ++j) {// 不购买第i个商品
      if (states[i-1][j] == true) states[i][j] = states[i-1][j];
    }
    for (int j = 0; j <= 3*w-items[i]; ++j) {//购买第i个商品
      if (states[i-1][j]==true) states[i][j+items[i]] = true;
    }
  }

  int j;
  for (j = w; j < 3*w+1; ++j) { 
    if (states[n-1][j] == true) break; // 输出结果大于等于w的最小值
  }
  if (j == 3*w+1) return; // 没有可行解
  for (int i = n-1; i >= 1; --i) { // i表示二维数组中的行，j表示列
    if(j-items[i] >= 0 && states[i-1][j-items[i]] == true) {
      System.out.print(items[i] + " "); // 购买这个商品
      j = j - items[i];
    } // else 没有购买这个商品，j不变。
  }
  if (j != 0) System.out.print(items[0]);
}

代码前半部分和 0-1 背包问题相同，我们主要看后半部分中是如何打印出选择购买哪些商品的。

状态 (i, j) 只有可能从 (i-1, j) 或者 (i-1, j-value[i]) 两个状态推导过来。所以，我们就检查这两个状态是否是可达的，也就是 states[i-1][j]或者 states[i-1][j-value[i]]是否是 true。

如果 states[i-1][j]可达，就说明我们没有选择购买第 i 个商品，如果 states[i-1][j-value[i]]可达，那就说明我们选择了购买第 i 个商品。我们从中选择一个可达的状态（如果两个都可达，就随意选择一个），然后，继续迭代地考察其他商品是否有选择购买。

内容小结

本节不涉及动态规划的理论，只是利用两个例子，展示了动态规划是如何解决问题的，并且一点一点详细给你讲解了动态规划解决问题的思路。

从例子中发现，大部分动态规划能解决的问题，都可以通过回溯算法来解决，只不过回溯算法解决起来效率比较低，时间复杂度是指数级的。动态规划算法，在执行效率方面，要高很多。尽管执行效率提高了，但是动态规划的空间复杂度也提高了，所以可以说，动态规划是一种空间换时间的算法思想。

贪心、分治、回溯、动态规划，这四个算法思想有关的理论知识，大部分都是“后验性”的，也就是说，在解决问题的过程中，往往是先想到如何用某个算法思想解决问题，然后才用算法理论知识，去验证这个算法思想解决问题的正确性。

课后思考

下面为改造过的”杨辉三角“。每个位置的数字可以随意填写，经过某个数字只能到达下面一层相邻的两个数字。设你从第一层，往下移动，把移动到最底层所经过的所有数字之和，定义为路径的长度。编程求出从最高层移动到最底层的最短路径长度。

img

答：参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int[][] matrix = {{5},{7,8},{2,3,4},{4,9,6,1},{2,7,9,4,5}};

public int yanghuiTriangle(int[][] matrix) {
    int[][] state = new int[matrix.length][matrix.length];
    state[0][0] = matrix[0][0];
    for (int i = 1; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            if (j == 0) state[i][j] = state[i - 1][j] + matrix[i][j];
            else if (j == matrix[i].length - 1) state[i][j] = state[i - 1][j - 1] + matrix[i][j];
            else {
                int top1 = state[i - 1][j - 1];
                int top2 = state[i - 1][j];
                state[i][j] = Math.min(top1, top2) + matrix[i][j];
            }
        }
    }
    int minDis = Integer.MAX_VALUE;
    for (int i = 0; i < matrix[matrix.length - 1].length; i++) {
        int distance = state[matrix.length - 1][i];
        if (distance < minDis) minDis = distance;
    }
    return minDis;
}
------ 本文结束------
坚持原创技术分享，您的支持将鼓励我继续创作！

欢迎关注我的其它发布渠道