1

我一直在尝试将一个数组划分为两个非空的不相交子集，以使它们的总和相等。 

eg. A = {1,2,3,6,88,55,29}  
one possible answer = 1+2+3  and 6

我已经阅读了关于平衡分区问题的 mit 教程，但我的限制不同。我不必考虑整个集合 A（意味着 A1 U A2 不一定会导致 A）。另一个问题是 N 的限制。每个最多有 100 个不同的元素 (<= 100 ) 。
我也阅读 了与我的问题相关的这篇文章，但我什么也得不到。 

My present Algo -- 
p[1][a[0]] = 1
for i = 2 to n
   for j = 0 to n*n
     if( p[i][j] >= 2) stop

            p[i][j] += j - a[i] > 0 ? ( p[i-1][j] + p[i-1][j-a[i]] ):0
            p[i][j] += j == a[i] ? 1:0
            p[i][j] += j < a[i] ? p[i-1][j]:0

解释 ：

Search for sum j at position i. If we got count at position j >=2 means 
there are more than two possibilities for summing up to j.

这是我的示例工作代码

我知道这种方法不能处理不相交的集合，但我无法找出任何其他方法。

我正处于 Dynamic Prog 的学习阶段。我觉得有点困难。有人可以帮我找出我当前算法中的错误吗？

4

1 回答 1

1

您的代码似乎没有遍历所有子集。一组大小的幂集n有2^n-1非空元素，所以我认为这是算法复杂度的下限。您需要找到一种适当的方法来枚举子集，这与其他关于 SO的问题有关

通常，子集生成是通过逐个添加元素来生成的。如果您使用动态编程，这允许您在一次加法中计算单个集合的总和。事实上，如果你有{1,2,3,6}并将值保存到12，你只需要添加88即可找到 的总和{1,2,3,6,88}。

您可以在基本 DP 之外找到进一步的优化。例如，如果您测试

 {88} > {1,2,3,6,29}

首先，您不需要{1,2,3,6,29}使用{88}. 同时你不需要测试任何包含 88 的集合{1,2,3,6,29}，因为它总是更大......现在它需要使用从更大的集合到更小的集合的递归。

于 2012-06-10T07:58:12.323 回答