10

我知道这在这里讨论了很多，但我正在努力解决这个问题。

我们有一组数字，例如 [3, 1, 1, 2, 2, 1]，我们需要将其分成两个子集，因此每个和都相等或差异最小。

我看过wikipedia entry、 this page (problem 7) 和blog entry。

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

4

4 回答 4

4

伪多项式算法旨在为决策问题提供答案，而不是优化问题。但是，请注意，示例中布尔值表中的最后一行表示当前集合能够总计为 N/2。

在最后一行中，取布尔值所在的第一列true。然后，您可以检查给定列中集合的实际值是多少。如果集合总和值为 N/2，则您已找到分区的第一组。否则，您必须检查哪个集合能够与 N/2 不同。您可以使用与上述相同的方法，这次是差异d。

于 2012-10-08T12:05:13.860 回答
1

这将是O(2^N)。这里没有使用动态规划。执行函数后可以打印result1、result2和差异。我希望这有帮助。

vector<int> p1,p2;
vector<int> result1,result2;
vector<int> array={12,323,432,4,55,223,45,67,332,78,334,23,5,98,34,67,4,3,86,99,78,1};

void partition(unsigned int i,long &diffsofar, long sum1,long sum2)
{
    if(i==array.size())
    {
        long diff= abs(sum1 - sum2);
        if(diffsofar > diff)
        {
            result1 =  p1;
            result2 = p2;
            diffsofar = diff;
        }
        return;
    }

    p1.push_back(array[i]);
    partition(i+1,diffsofar,sum1+array[i],sum2);
    p1.pop_back();

    p2.push_back(array[i]);
    partition(i+1,diffsofar,sum1,sum2+array[i]);
    p2.pop_back();

    return;
}
于 2014-11-29T18:13:59.013 回答
0

我最近遇到了同样的问题，我发布了一个关于它的问题（这里：Variant of Knapsack）。在我的情况下，不同之处在于结果子集的大小必须相同（如果原始集合具有偶数个元素）。为了确保这一点，我在@Sandesh Kobal 的答案中添加了几行；

void partition(unsigned int i,long &diffsofar, long sum1,long sum2)
{
    int maxsize = (array.size()+1)/2;

    if(p1.size()>maxsize)
        return;

    if(p2.size()>maxsize)
        return;

    if(i==array.size())
    {
        ...

此外，在两次调用之后partition，我添加了if(diffsofar==0) return;. 如果我们已经找到了最佳解决方案，那么继续搜索是没有意义的……

于 2016-01-30T01:02:30.207 回答
0

我看过的所有文章都采用动态编程方法。我们真的需要一个吗？

假设给定的数组是arr

使用以下算法：

  1. 按降序对数组进行排序
  2. 创建两个空数组，a = []然后b = []
  3. sum_a = sum_b = 0
for x in arr:
    if sum_a > sum_b:
        b.append(x)
        sum_b += x
    else:
        a.append(x)
        sum_a += x

sum_a和之间的绝对差异sum_b是两个子集之间可能的最小差异。


考虑arr = [3,1,1,2,2,1]

对数组进行排序：arr = [3,2,2,1,1,1]

a = [], b = []
a = [3], b = []
a = [3], b = [2]
a = [3], b = [2,2]
a = [3,1], b = [2,2]
a = [3,1,1], b = [2,2]
a = [3,1,1], b = [2,2,1]

sa = 5, sb = 5

最小差异：5 - 5 = 0

于 2021-09-19T06:53:51.657 回答