8

我的问题是关于 CodeFu 练习题（2012 年第 2 轮问题 3）。它基本上归结为将整数数组分成两个（几乎）相等的一半，并返回两者之间的最小可能差异。我在下面包含了问题描述。正如评论中所指出的，这可以描述为一个平衡分区问题，这是一个动态规划领域的问题。

现在已经讨论了很多类似的问题，但我无法为这个特定的问题找到有效的解决方案。问题当然是，对于蛮力搜索（至少在使用递归时），要遍历的可能组合的数量很快就会变得太大。我有一个递归解决方案，它适用于除最大问题集之外的所有问题。我尝试添加一些优化以提前停止递归，但性能仍然太慢，无法在 CodeFu 允许的 5 秒最大值内解决一些最大长度（30）的数组。任何有关如何改进或重写代码的建议都将受到欢迎。我也很想知道它是否有助于制作迭代版本。

更新：在这个很好的网站上有一个关于平衡分区问题的理论讨论，它很好地说明了如何以动态方式进行和解决这个问题。这确实是我所追求的，但我不知道如何将理论付诸实践。电影中提到可以“使用反向指针的旧技巧”找到两个子集合中的元素，但我不明白如何。

问题

你和你的朋友有许多不同数量的硬币。您需要将硬币分成两组，以使这些组之间的差异最小。

例如，大小为 1,1,1,3,5,10,18 的硬币可以拆分为： 1,1,1,3,5 和 10,18 1,1,1,3,5,10 和 18 或 1 ,1,3,5,10 和 1,18 第三种组合是有利的，因为在这种情况下，组之间的差异仅为 1。约束：硬币将具有 2 到 30 个元素，包括硬币的每个元素将介于 1 和100000 含

返回值：将硬币分成两组时可能的最小差异

注意：CodeFu 规则规定在 CodeFu 的服务器上执行时间不得超过 5 秒。

主要代码

Arrays.sort(coins);

lower = Arrays.copyOfRange(coins, 0,coins.length-1);
//(after sorting) put the largest element in upper
upper = Arrays.copyOfRange(coins, coins.length-1,coins.length);            

smallestDifference = Math.abs(arraySum(upper) - arraySum(lower));
return findSmallestDifference(lower, upper, arraySum(lower), arraySum(upper), smallestDifference);

递归代码

private int findSmallestDifference (int[] lower, int[] upper, int lowerSum, int upperSum, int smallestDifference) {
    int[] newUpper = null, newLower = null;
    int currentDifference = Math.abs(upperSum-lowerSum);
    if (currentDifference < smallestDifference) {
        smallestDifference = currentDifference;
    } 
    if (lowerSum < upperSum || lower.length < upper.length || lower[0] > currentDifference 
            || lower[lower.length-1] > currentDifference 
            || lower[lower.length-1] < upper[0]/lower.length) {
        return smallestDifference;
    }
    for (int i = lower.length-1; i >= 0 && smallestDifference > 0; i--) {           
       newUpper = addElement(upper, lower[i]);
       newLower = removeElementAt(lower, i);
       smallestDifference = findSmallestDifference(newLower, newUpper, 
               lowerSum - lower[i], upperSum + lower [i], smallestDifference);
    }
    return smallestDifference;
}

数据集

这是一个需要很长时间才能解决的集合的示例。

{100000,60000,600,600,600,60000,600,600,600,60000,60000,60000,60000,60000,600,600,600,600,600,600,600,60000,600,600,60000,60000,600,60000,600,600,600,60000,600,600,600,60000,600,600,600,60000,60000 ,60000,60000, 60000,60000,60000}

如果您想要完整的源代码，我已将其放在Ideone上。

4

2 回答 2

3

编辑 只是为了清楚：在问题中指定在五秒内运行的额外限制之前，我已经写了这个答案。我也写了它只是为了表明有时蛮力是可能的，即使它看起来不是。所以这个答案并不意味着是这个问题的“最佳”答案：它恰恰意味着是一个蛮力解决方案。作为一个附带好处，这个小解决方案可以帮助某人编写另一个解决方案，以在可接受的时间内验证他们对“大”数组的回答是否正确。

问题当然是，要遍历的可能组合的数量很快就会变得太大而无法进行蛮力搜索。

鉴于最初陈述的问题（在指定最大运行时间 5 秒之前），我完全不同意该陈述；）

您特别写道，最大长度为 30。

请注意，我不是在谈论其他解决方案（例如，考虑到您的限制，可能会或可能不会工作的动态编程解决方案）。

我要说的是2 30并不大。它有点多于十亿，仅此而已。

现代 CPU 可以在一个内核上每秒执行数十亿个周期。

你不需要递归来解决这个问题：递归会破坏你的堆栈。有一种简单的方法可以确定所有可能的左/右组合：简单地从 0 计数到 2 exp 30 - 1 并检查每一位（决定，比如说，有点打开意味着你把值放在左边，关闭意味着你把右边的值）。

因此，如果我没有记错以下方法，那么给出问题陈述，没有任何优化，应该可以工作：

  public static void bruteForce( final int[] vals) {
    final int n = vals.length;
    final int pow = (int) Math.pow(2, n);
    int min = Integer.MAX_VALUE;
    int val = 0;
    for (int i = pow -1; i >= 0; i--) {
        int diff = 0;
        for ( int j = 0; j < n; j++ ) {
            diff += (i & (1<<j)) == 0 ? vals[j] : -vals[j];

        }
        if ( Math.abs(diff) < min ) {
            min = Math.abs(diff);
            val = i;
        }
    }

    // Some eye-candy now...
    for ( int i = 0 ; i < 2 ; i ++ ) {
        System.out.print( i == 0 ? "Left:" : "Right:");
        for (int j = 0; j < n; j++) {
            System.out.print(((val & (1 << j)) == (i == 0 ? 0 : (1<<j)) ? " " + vals[j] : ""));
        }
        System.out.println();
    }
}

例如：

bruteForce( new int[] {2,14,19,25,79,86,88,100});
Left: 2 14 25 79 86
Right: 19 88 100


bruteForce( new int[] {20,19,10,9,8,5,4,3});
Left: 20 19
Right: 10 9 8 5 4 3

在 30 个元素的数组上，在我便宜的 CPU 上，它运行时间为 125 秒。那是针对“初稿”，在单核上运行的完全未优化的解决方案（所述问题对于并行化来说是微不足道的）。

您当然可以变得更漂亮并重用大量中间结果，从而在不到 125 秒的时间内解决包含 30 个元素的数组。

于 2012-10-31T13:32:59.073 回答
2

说N是所有硬币的总和。我们需要找到一个硬币子集，其中硬币的总和最接近N/2。让我们计算所有可能的总和并选择最好的一个。在最坏的情况下，我们可能期望 2^30 个可能的总和，但这可能不会发生，因为最大可能的总和是 100K*30，即 3M - 远小于大约 1G 的 2^30。因此，一个 3M 整数或 3M 位的数组应该足以容纳所有可能的总和。

所以我们有数组a，a[m] == 1当且仅当m是一个可能的总和。

我们从零数组开始，并且有a[0]=1，因为总和0是可能的（一个没有硬币）。

for (every coin)
  for (int j=0; j<=3000000; j++)
    if (a[j] != 0)
      // j is a possible sum so far
      new_possible_sum = j + this_coin
      a[new_possible_sum] = 1

当您完成 30 * 3M 步时，您将知道所有可能的总和。找出m最接近的数N/2。你的结果是abs(N-m - m)。我希望我能适应时间和记忆的界限。

编辑：需要更正和 2 个优化：

  1. 按降序遍历数组。否则一美元硬币会一次性覆盖整个数组。
  2. 将数组的大小限制为N+1（包括 0），以更快地解决较小的硬币组。
  3. 由于我们几乎总是得到 2 个相同的结果：m和N-m，将数组大小减小到N/2。为 .添加绑定检查new_possible_sum。扔掉更大的可能金额。
于 2012-10-31T18:09:39.890 回答