平衡分区 [英] Balanced partition

问题描述

我知道这是谈了很多在这里，但我在努力解决这个问题。

I know this was talked over a lot here, but I am struggling with this problem.

我们有一组数字，例如[3，1，1，2，2，1]，我们需要打破它分成两个子集，所以每个总和等于或差是最小的。

We have a set of numbers, e.g [3, 1, 1, 2, 2, 1], and we need to break it into two subsets, so the each sum is equal or difference is minimal.

我见过百科词条，这的页面（问题7）和博客条目。

I've seen wikipedia entry, this page (problem 7) and a blog entry.

但列出的每个算法只给YES / NO的结果，我真的不知道如何使用它们来打印出两个子集（例如S1 = {5,4}和S2 = {5,3，3}） 。我缺少的是在这里吗？

But every algorithm listed is giving only YES/NO result and I really don't understand how to use them to print out two subsets (e.g S1 = {5, 4} and S2 = {5, 3, 3}). What am I missing here?

推荐答案

伪多项式算法的目的是提供一个答案的的决定问题的，不是的优化问题。但是，请注意，在布尔值的表中的最后一排的例子表示当前一套能够总结为N / 2。

The pseudo-polynomial algorithm is designed to provide an answer to the decision problem, not the optimization problem. However, note that the last row in the table of booleans in the example indicates that the current set is capable of summing up to N/2.

在最后一排，把第一列，其中布尔值真。然后，您可以检查一下集的给定列中的实际值。如果该套合计为N / 2，你已经找到了第一组的分区。否则，你要检查哪组是能够被区别为N / 2。您可以使用同样的方法如上，这个时间差的ð的。

In the last row, take the first column where the boolean value is true. You can then check what the actual value of the set in the given column is. If the sets summed value is N/2 you have found the first set of the partition. Otherwise you have to check which set is capable of being the difference to N/2. You can use the same approach as above, this time for the difference d.

这篇关于平衡分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！