2

我以前偶然发现过这个问题，这是一个平衡问题。该程序接收一个大小为 n 的整数数组。然后程序确定这个整数数组是否可以分成两个相等的部分，每半部分的整数之和相等。

前任。1 2 3 8 10 4

其中，程序返回true，这意味着它可以分成两半，每半14

我知道这与组合/排列有关，我对它们并不是很擅长。我只是设法想到了蛮力方法。这可以使用任何其他方法解决吗？也许更有效的算法？

一步一步的解决方案将非常有帮助。非常感谢

4

3 回答 3

2

只是给它一些非常简短的想法：

  • 这个问题等价于找到重量正好是卵石总重量一半的任何卵石子集
  • 如果最重的卵石重量超过卵石总重量的一半，则没有解决方案
于 2011-02-09T09:17:45.273 回答
1

这是分区问题，可以很容易地看出它等同于子集和问题和背包问题。它是 NP-Complete 的，人们认为你不能比详尽列出所有组合做得更好。

您可以轻松检查所有可能的方式：对于每个元素，它要么在左半边，要么在右半边。

于 2011-02-09T09:34:58.863 回答
0

看看我对这个问题的回答。您的问题本质上是相关的。你必须找出你可以用这些数字达到的总和。如果 sum:total_sum / 2可以实现，那么您已经找到了解决方案:)

于 2011-02-09T08:21:55.307 回答