我有以下任务。
您有一个包含 1<=N<=22 个元素的多重集 S。 每个元素的正值最多为 10000000。
假设S有两个子集s1和s2，其中一个子集所有元素的值之和等于另一个子集所有元素值之和，且为最大可能值。我必须返回 S 的哪些元素不会包含在两个子集中。
它可能之前已经解决了，我认为它是Partition problem的一些变体。但我找不到它。如果有人能指出我正确的方向，那就太好了。
编辑:一个元素不能同时存在于两个子集中。
最佳答案
这是子集和的变体，可以通过增加问题的维度(和 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 (因为可能不止一个)
在找到解决方案( x 中 D(n,x,x) 的值)后，可以通过回溯 DP 矩阵并重新跟踪您的步骤来完成对元素本身的查找，如针对类似问题所解释的，例如: How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?
该解决方案的总复杂度为 O(SUM^2 * n)
关于algorithm - 寻找分区问题算法返回 true 的最大值子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31819009/