将一个数组最优地分成两个子数组，使得两个子数组中元素的和相等。

Question

我需要翻译这个方程：

    n = 7
    1 + 1 - 4 - 4 - 4 - 2 - 2

我该如何最佳地替换运算符，使得方程式的总和等于零，或者打印-1。

我想到了一种算法，但它不是最优解。我有一个想法，用O(n*2^n)的复杂度暴力破解所有情况，但(n<300)。

这是问题的链接: http://codeforces.com/gym/100989/problem/M。

- Santa K.

Answer 1

你正在尝试解决分割问题；即将整数分成两个子集，使它们的和相等，并为一个子集中的整数分配正号，另一个子集中的整数分配负号。

在你的特定问题中，你对整数数量和值都有较低的限制。你可以采用标准的动态算法方法与包含/排除方法；即通过考虑最后一个整数未被使用的情况（因此需要一个前n-1个整数的子集，其总和为i），以及最后一个整数被使用的情况（一个前n-1个整数的子集，其总和为i - val(n)）来找到前n个整数的子集，其总和为i。

- borrible

---

虽然这个链接可能会回答问题，但最好在此处包含答案的基本部分并提供参考链接。仅有链接的答案如果链接页面更改可能会变得无效。-【来自评论】 - Enamul Hassan

@manetsus - 回答的文本给出了关键点，即OP试图回答的问题名称。在这种情况下，链接并不是回答问题所必需的；它只是锦上添花。 - borrible

Answer 2

这里有一个想法：

1. 将第二个到第N个元素按降序排序（问题保持不变）。
2. 反向累加求和。[1 4 3 2] => [10 9 5 2]，以获取剩余整数中仍然可以达到的最大数字的上限。
3. 使用反向累积和的边界进行剪枝。

在Java中实现：

// assuming the numbers are positive
// (ignore operator when parsing, line.split("[ +-]+") will do)
public static int canReach0(int[] numbers) {
  sort(numbers, 1); // sort(array, offset) doesn't matter what algorithm
                    // for 300 elements and compared to the complexity of the rest
  int[] revSum = new int[numbers.length];
  revSum[numbers.length - 1] = numbers[numbers.length - 1];
  for (int i = numbers.length - 2; i >= 0; i--)
    revSum[i] = revSum[i + 1] + numbers[i];
  int sum = numbers[0];
  if (sum == revSum[1])
    return 0;
  return solve(numbers, 1, sum, revSum);
}

private static int solve(int[] numbers, int index, int sum, int[] revSum) {
  if (index == numbers.length - 1)
    return -1;
  int high = sum + numbers[index];
  if (high == revSum[index + 1] || 
      (high < revSum[index + 1] && solve(numbers, index + 1, high, revSum) == 0))
    return 0;
  int low = sum - numbers[index];
  if (low == -revSum[index + 1] ||
      (low > -revSum[index + 1] && solve(numbers, index + 1, low, revSum) == 0))
    return 0;
  return -1;
}

- maraca