2

我有以下任务。

您有一个包含 1<=N<=22 个元素的多重集 S。每个元素的正值最大为 10000000。

假设 S 有两个子集 s1 和 s2，其中一个的所有元素的值之和等于另一个的所有元素的值之和，并且它是可能的最大值。我必须返回 S 的哪些元素不会包含在两个子集中的任何一个中。

它之前可能已经解决了，我认为它是分区问题的一些变体，但我找不到它。如果有人能指出我正确的方向，那就太好了。

编辑：一个元素不能在两个子集中。

4

2 回答 2

1

这是子集和的变体，可以通过增加问题（和 DP 矩阵）的维度来类似地解决，然后对子集和应用与原始解决方案非常相似的解决方案，该解决方案遵循递归公式：

D(i,x,y) = D(i-1,x,y)   OR    D(i-1,x-l[i],y)    OR    D(i-1,x,y-l[i])
             ^                       ^                       ^ 
           not chosen        chosen for first set         chosen for 2nd set

和基本条款：

D(0,0,0) = true
D(0,x,y) = false        x!=0 or y!=0
D(i,x,y) = false        x<0 or y<0

在计算完这个问题的 DP 矩阵（实际上是 3d 数组）之后，你所要做的就是找到是否有任何条目D(n,x,x) == true，对于某些x<= SUM/2（其中SUM是整个原始集合的总和），找出是否有任何可行的解决方案.
因为你想要最大值，所以答案应该是这样的最大值x（D(n,x,x)=true因为可能不止一个）

在找到解决方案（xin的值D(n,x,x)）之后，可以通过跟踪 DP 矩阵并回溯您的步骤来查找元素本身，如对类似问题的解释：How to find which elements are in the bag, using Knapsack Algorithm [而不仅仅是包的价值]？

该解决方案的总复杂度为O(SUM^2 * n)

于 2015-08-04T22:22:18.677 回答
1

将 S 尽可能均匀地划分为 T ∪ U （如果有的话，将额外的元素放入 U 中）。将 T 的三向分区循环到 A ∪ B ∪ C（≤ 3 11 = 177,147 个）。存储项目 |sum(A) - sum(B)| → C 到一个映射中，只保留总和最小的值，以防键已经存在。

将 U 的三路分区循环到 D ∪ E ∪ F。查找 |sum(D) - sum(E)| 在地图中；如果它以值 C 存在，则将 C ∪ F 视为排除元素的可能性（具有相等和的两个部分是 A ∪ D 和 B ∪ E，或 A ∪ E 和 B ∪ D）。

于 2015-08-05T00:50:57.717 回答