平衡分区

10

我知道这个问题已经在这里讨论了很多次,但我还是遇到了麻烦。

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

我看过维基百科的条目,这个页面(问题7)和一个博客文章

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


你可以通过反向遍历计算表来获取子集。这是动态规划问题中的标准策略。 - Nabb
你能否详细阐述一下这个问题? - spacevillain
你的列表中最多可以有多少个数字?如果算法产生的解决方案非常接近最优解但不一定是最优解,那是否足够好? - Bob Bryan
没有最大限制,我真的需要尽可能最好的解决方案 :-) - spacevillain
4个回答

4
伪多项式算法旨在回答决策问题而不是优化问题。但是,请注意,在示例的布尔表格中,最后一行表示当前集合可以加起来等于N/2。
在最后一行中,取第一个布尔值为true的列。然后可以检查给定列中集合的实际值。如果集合的总和为N/2,则找到了第一组划分集。否则,必须检查哪个集合能够成为N/2的差异。可以使用与上述相同的方法,这次要寻找差异d。

1
这将是O(2^N)的时间复杂度。这里没有使用动态规划。您可以在函数执行后打印result1、result2和difference,希望这能有所帮助。
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;
}

0

我最近也遇到了同样的问题,并发布了一个相关问题(这里是:0/1背包问题)。不同之处在于,如果原始集合有偶数个元素,则结果子集必须具有相同的大小。为了确保这一点,我在@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;。如果我们已经找到了最优解,继续搜索就没有意义了...

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_asum_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


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接