问题

有一堆石头，每块石头的重量都是正整数。每次从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x≤y。那么粉碎的可能结果如下：
如果 x 与 y 相等，那么两块石头都会被完全粉碎；
否则，重量为 x 的石头将会完全粉碎，而重量为 y 的石头的新重量为 y−x。
最后，最多只会剩下一块石头。返回此时石头最小的可能重量。如果没有石头剩下，就返回 0。

  1. 示例：
  3. 输入：[1, 2, 1, 7, 9, 4]
  4. 输出：
  5. 解释：Round 1: (2, 4) -> 2, 数组变成 [1, 1, 7, 9, 2]
  6.      Round 2: (7, 9) -> 2, 数组变成 [1, 1, 2, 2]
  7.      Round 3: (2, 2) -> 0, 数组变成 [1, 1]
  8.      Round 4: (1, 1) -> 0, 数组为空，返回 0

问题分析

转化成动态规划问题

首先，请你观察一下上面提供的示例。在示例中，第一步组合 2 和 4，求出 (4 - 2) = 2；第二步组合 7 和 9，求出 (9 - 7) = 2；第三步组合 2 和 2，求出 (2 - 2) = 0；最后第四步组合 1 和 1，同样得 0。我们把这个过程组合成一个式子，它看起来是这样的：
1−(1−((4−2)−(9−7)))
如果解开这些括号，就可以得到如下式子：
1+2+9−1−4−7
这个时候，我们可以把这个公式分成两组，一组是从数组中挑选出几个数字相加；然后，将另外几个数字相减，求两个数字的差。最后确保这个差最小。
从直觉上来说，如何确保两组数字之差最小呢？

我们可以看到如果一组数字接近所有数字之和的 1/2，那么两组数字之差肯定越小，比如上面的示例中所有数字之和是 24，所以一组数字是 12，另一组数字也是 12，最后肯定能得到最小值 0。

现在，假设有一个背包，背包的容量是 12（24/2）。接着，我们有一堆的物品，重量分别是 [1, 2, 1, 7, 9, 4]，注意我们设它的价值与重量相同。现在我们希望选出的物品放到背包里的价值最大，这样一来，我们就可以把这个题目转化成 0-1 背包问题了。

代码实现：

  1. public class CrushStoneDemo {
  3.     public static void main(String[] args) {
  4.         // 前面填充0，表示第0块碎石
  5.         int[] w = new int[]{0, 1, 2, 1, 7, 9, 4};
  6.         // 重量和价值相同
  7.         int max = dp(w, w, 6, 12);
  8.         System.out.println("剩余最小的碎石重量为：" + Math.abs((24 - max) - max));
  9.     }
  11.     /**
  12.      * 将碎石问题转换为0-1背包问题
  13.      *
  14.      * @param w 每个碎石的重量
  15.      * @param v 每个碎石的价值，这里与重量相等
  16.      * @param N 碎石数量
  17.      * @param W 背包问题的容量，这里若有碎石重量的一半
  18.      * @return 剩余碎石的重量
  19.      */
  20.     public static int dp(int[] w, int[] v, int N, int W) {
  21.         // 创建备忘录
  22.         int[][] dp = new int[N + 1][W + 1];
  23.         //
  24.         for (int tn = 1; tn < N + 1; tn++) {
  25.             for (int rw = 1; rw < W + 1; rw++) {
  26.                 //
  27.                 if (rw < w[tn]) {
  28.                     // 不选
  29.                     dp[tn][rw] = dp[tn - 1][rw];
  30.                 } else {
  31.                     //
  32.                     dp[tn][rw] = Math.max(dp[tn - 1][rw], dp[tn - 1][rw - w[tn]] + v[tn]);
  33.                 }
  34.             }
  35.         }
  36.         return dp[N][W];
  37.     }
  38. }

输出

剩余最小的碎石重量为：0