0

例子：

输入：3、6、3 输出：真（因为 3 + 3 = 6）

输入：3、2、6、4 输出：False（因为没有组合会导致相等）

输入：4、7、3、6 输出：真（因为 4 + 6 = 7 + 3）

你们能给我一个关于如何编码的想法吗？我已经开始学习如何编码，但我对如何添加数字并比较它们感到困惑

4

5 回答 5

3

我将解释一个人如何在不知道魔术词（如“分区问题”、“动态编程”等）的情况下解决这个问题，以查阅一些大书的答案（如维基百科）。

如果您从输入中取出一个尚未使用的最大数字的实例并将其分配给您的两组之一，那么您已将问题简化为同一问题的较小实例（广义版本）。

广义的问题是，您能否将输入数字分成两组，使得两组总和之间的差值是一个特定的非负整数？

假设我们的输入数字是 4, 3, 2, 1，我们需要创建两个组，使组和之间的差为 0。

我们将 4 分配给其中一个组，在这种特殊情况下，哪个组都没有关系。

现在我们剩下的输入数字是 3, 2, 1，忽略我们已经处理过的 4，我们需要将这三个数字分成两组，这样两组之和之间的差是 4。（这将平衡我们通过将 4 分配给其中一个组来创建两个组之间的差异。）正如所承诺的，这是原始问题类型的一个较小的实例。

困难在于，有时，例如 5、5、4、3、3（维基百科“分区问题”中的示例），下一个数字需要进入哪个组并不明显。如果你跟踪你所做的事情，那么当你发现你最近的尝试没有奏效时，你可以回来（“回溯”）并尝试另一种方式。

5, 5, 4, 3, 3 {} {}
   5, 4, 3, 3 {5} {}
      4, 3, 3 {5} {5}
         3, 3 {5, 4} {5}
            3 {5, 4} {5, 3}
              {5, 4} {5, 3, 3} NO - backtrack
              {5, 4, 3} {5, 3} NO - backtrack
            3 {5, 4, 3} {5}
              {5, 4, 3} {5, 3} NO - already tried - backtrack
              {5, 4, 3, 3} {3} NO - backtrack
         3, 3 {5} {5, 4} NO - symmetric to what we already tried - backtrack
      4, 3, 3 {5, 5} {}
         3, 3 {5, 5} {4}
            3 {5, 5} {4, 3}
              {5, 5} {4, 3, 3} YES

我们能很快得到答案吗？好吧，这不是被问到的问题，但鉴于回溯的复杂性，问这个问题是很自然的。答案是，不，即使我们有世界历史上最聪明的人为我们工作。从来没有人找到一种方法，无论我们给出什么样的问题实例，都能保证快速执行。也许我们可以很好地处理这些问题的许多实例，但总的来说，平均而言，做这种事情的程序注定会很慢。

于 2013-03-14T02:42:56.260 回答
2

这就是划分问题，它是 NP 完全的。尽管如此，您仍然可以使用动态编程解决方案。请参阅维基百科文章。

http://en.wikipedia.org/wiki/Partition_problem

于 2013-03-14T03:15:11.087 回答
0 
public class Weirdie {
private boolean calculate(int[] array) {
    boolean match = false;
    List<Integer> list = new ArrayList<Integer>();
    int length = array.length;
    for(int i=0;i<length;i++) {
        for(int j=i+1;j<length;j++) {
            int sum = array[i] + array[j];
            if(list.contains(sum)) {
                match = true;
                break;
            } else {
                list.add(sum);
            }
        }
        if(match) {
            break;
        }
    }
    return match;
}

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = { 3, 6, 3, 4, 8};
    int[] array2 = { 3, 2, 6, 4};
    int[] array3 = { 4, 7, 3, 6 };
    Weirdie  w = new Weirdie();
    System.out.println(w.calculate(array));
    System.out.println(w.calculate(array2));
    System.out.println(w.calculate(array3));
}

}

实际上我仍然对您的要求感到困惑。正如您的描述，数字组 1 {3,6,3} 将输出 true 因为 3+3=6。而您说数字组 2 {3,2,6,4} 将输出错误，但显然 2+4=6 也符合您的条件。对于您的第三个数字组，我认为数字组 1 输出 true 的原因是 3+6=6+3。

于 2013-03-14T04:53:29.790 回答
0

好的！只使用蛮力计算，我检查每一个可能的选项

int[] numbersArray = new int[10];
int sum = 0;

for(int j = 0; j < numbersArray.lenght;j++) // sum
   sum += numbersArray[j];



for(int i = 0; i < numbersArray.lenght;i++)
{
   int numChecking =  numbersArray[i]; // right half .. 

   if((sum-numChecking) == numChecking)
     return true;

}
return false;

// 我还没有测试过，但是，这将检查所有可能性的 1 值..

于 2013-03-14T18:52:19.423 回答
0

要确定一个数组是否可以分成两个相等的和数组，我们也可以找到一个子集，它具有整个数组之和的一半。

例如：输入：4、7、3、6

我们应该找到一个总和 == 10 的子集，这是一个简单的 DP 概率。

公共静态布尔 isSubset(int[] a, int sum, int n) {

  if(sum == 0)
    return true;
  if(n<0)
    return false;
 return isSubset(a, sum-a[n], n-1) || isSubset(a, sum, n-1);
}
于 2013-03-14T06:51:47.877 回答