1

所以我有10个号码。可以说每个数字代表一个人的技能。如果我要创建 2 个 5 人的团队，我将如何组成 2 个团队，以使他们的团队总和的差异最小。

4

7 回答 7

2

对于 10 个数字，最简单的方法是检查所有组合并计算差异。

于 2013-06-30T14:45:40.247 回答
1

这类似于背包问题：您尝试将个人放在其中一个团队中，以使该团队的总和最大不大于总和的一半。如果团队规模不受限制，那将是相同的。

于 2013-06-30T14:58:19.120 回答
0

我刚刚试了一下——不幸的是，我不得不对排列的东西（函数next）进行编程并调用result.fit每个元素。可以做得更好，但为了演示它应该足够好。

var all = [ 3, 4, 5, 8 , 2, 1, 1, 4, 9, 10 ];

function sumArray(a) {
    var asum = 0;
    a.forEach(function(v){ asum += v });
    return asum;
}

var next = function(start, rest, nbr, result) {
    if (nbr < 0) {
        result.fit(start);
        return;
    }
    for (var i = 0; i < rest.length - nbr; ++i) {
        var clone = start.slice(0);
        clone.push(rest[i]);
        next(clone, rest.slice(i + 1), nbr - 1, result);
    }
};

var result = {
    target: sumArray(all) / 2,
    best: [],
    bestfit: Math.pow(2,63),    // really big
    fit: function(a) {
        var asum = sumArray(a);
        var fit = Math.abs(asum - this.target);
        if (fit < this.bestfit) {
            this.bestfit = fit;
            this.best = a;
        }
    }
}

next([], all, all.length / 2, result);
console.log(JSON.stringify(result.best));
于 2013-07-01T12:04:09.247 回答
0

这是分区问题的一个实例，但对于您的小实例测试所有组合应该足够快。

于 2013-07-02T10:00:06.153 回答
0

这是我想出的一个疯狂的想法。

时间复杂度：O(N log N)

  1. 对数字进行排序。
  2. 找到我们想要命中的集合（ T ）的目标总和（所有值的总和/2）
  3. 令Q = 排序列表中前 5 个数字的集合。Q将是我们的最终集，我们将对其进行迭代改进。
  4. for(each element q from last element to first element of Q)
{
 Find a number p that is not currently used
 which if swapped with the current element q   
 makes the sum closer to T but not more than T.
 Remove q from Q
 Add p to Q
}
return Q as best set.

虽然 for 循环看起来好像是 O(N 2 )，但是可以进行二分搜索来找到数字 p。所以它是 O(N*log N)

免责声明：我只描述了算法。我不知道如何正式证明它。

于 2013-06-30T18:16:50.323 回答
0

与大多数算法相同——比较 126 种组合。Haskell 中的代码：

inv = [1,2,3,4,5,6,7,8,9,10]

best (x:xs) (a,b)
  | length a == 5 = [(abs (sum a - sum (x:xs ++ b)),(a,x:xs ++ b))]
  | length b == 5 = [(abs (sum (x:xs ++ a) - sum b),(x:xs ++ a,b))]
  | otherwise     = let s = best xs (x:a,b)
                        s' = best xs (a,x:b)
                    in if fst (head s) < fst (head s') then s
                       else if fst (head s') < fst (head s) then s'
                       else s ++ s'

main = print $ best (tail inv) ([head inv],[])

输出：

*Main> main
[(1,([9,10,5,2,1],[8,7,6,4,3])),(1,([10,8,6,2,1],[9,7,5,4,3]))
,(1,([9,10,6,2,1],[8,7,5,4,3])),(1,([9,8,7,2,1],[10,6,5,4,3]))
,(1,([10,8,7,2,1],[9,6,5,4,3])),(1,([9,10,4,3,1],[8,7,6,5,2]))
,(1,([10,8,5,3,1],[9,7,6,4,2])),(1,([9,10,5,3,1],[8,7,6,4,2]))
,(1,([10,7,6,3,1],[9,8,5,4,2])),(1,([9,8,6,3,1],[10,7,5,4,2]))
,(1,([10,8,6,3,1],[9,7,5,4,2])),(1,([9,8,7,3,1],[10,6,5,4,2]))
,(1,([10,7,5,4,1],[9,8,6,3,2])),(1,([9,8,5,4,1],[10,7,6,3,2]))
,(1,([10,8,5,4,1],[9,7,6,3,2])),(1,([9,7,6,4,1],[10,8,5,3,2]))
,(1,([10,7,6,4,1],[9,8,5,3,2])),(1,([9,8,6,4,1],[10,7,5,3,2]))
,(1,([8,7,6,5,1],[9,10,4,3,2])),(1,([9,7,6,5,1],[10,8,4,3,2]))]
于 2013-07-02T04:56:00.250 回答
0

生成 5 个元素的所有组合。您将在一个团队中拥有这 5 个，而其余的将在另一个团队中。比较所有结果并选择差异最小的一个。for您可以使用 5 个循环创建所有这些组合。

于 2013-06-30T21:30:34.027 回答