平衡鹅卵石问题

2011-02-09 58 views 2 likes

我以前就偶然发现过这个问题，这是一个平衡问题。该程序需要一个大小为n的整数数组。程序然后确定这个整数数组是否可以分成2个相等的部分，每个半部分的整数和相等。平衡鹅卵石问题

ex。其中1 2 3 8 10 4

，程序返回真，这意味着它可以与14中的每个

我知道这是关于组合/排列被分成两个半部和我不是真的很善于他们。我只想到了蛮力法。这可以使用任何其他方法解决吗？更高效的算法可能？

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

2011-02-09 maru

您可能想看看：http://en.wikipedia.org/wiki/Partition_problem – DhruvPathak 2011-02-09 08:22:07

我记得手指树数据结构。可能有一些方法可以使用它来获得增量解决方案。 – ony 2011-02-09 08:44:46

回答

这是Partition Problem可容易被看作是等同于Subset Sum Problem和Knapsack Problem。它是NP完全的，并且认为你不可能比所有组合的详尽列表做得更好。

您可以方便地检查所有可能的方式：对于每个元素，它在左半部分或右半部分。

2011-02-09 09:34:58 wnoise

看看我的答案this问题。你的问题是至关重要的。你必须找到你可以用数字实现的总和。如果总和：total_sum/2然后可以实现你已经找到了解决办法:)

2011-02-09 08:21:55

只是付出一些非常短的念头：

2011-02-09 09:17:45