0

问题：
给你一个整数权重列表。您需要将这些权重分配到两组中，以使每组总权重之间的差异尽可能小。
输入数据：权重列表。
输出数据：代表最小可能重量差异的数字。

我看到了答案，但我不明白为什么 bestval = -1。谁能帮我弄清楚？多谢！
代码如下：

import itertools;

def checkio(stones):

    total = 0
    for cur in stones:
        total += cur

    bestval = -1

    for i in range(0,len(stones)):
        for comb in itertools.combinations(stones,i):
            weight = 0
            for item in comb:
                weight += item
            d = diff(total - weight, weight)
            if bestval == -1 or d < bestval:
                bestval = d                    
    return bestval

def diff(a,b):
    if a >= b:
        return a - b
    else:
        return b - a
4

4 回答 4

2

这是一个您知道不可能正确的起始值，因此无论多么糟糕，它都会被第一个答案取代！

于 2013-06-26T14:45:37.730 回答
1

bestval最初只是设置为 -1 并在循环中第一次更新为d. 之后，bestval每次都会再次更新，这d是一个比当前更好的值（也就是更小的权重差异）bestval。

关键代码在这里...

if bestval == -1 or d < bestval:
    bestval = d

所以在循环的第一次通过时，bestval == -1是真的，并且bestval被更新了。之后，d < bestval检查确定是否更新该值。

于 2013-06-26T14:46:06.527 回答
0

我怀疑通过所有组合是解决问题的蛮力和缓慢的方法。

按大小对重量进行排序，然后从最重到最轻，根据桩之间的重量差异将它们一一添加到左侧或右侧，这可能会给出最佳答案。

下面的伪代码，使其成为 O(n) 问题（如果忽略排序）；

sort weights into stack;
while (weight = pop stack) {
  if (sum(left) - sum(right) > 0) push weight on right
  else push weight to left;
}
bestval = sum(left) - sum(right);

例如 { 1, 2, 3, 4}

0. l 0 r 0 => 0 add 4 to left
1. l 4 r 0 => +4 add 3 to right
2. l 4 r 3 => +1 add 2 to right
3. l 4 r 5 => -1, add 1 to left
4. l 5 r 5 => same
于 2013-06-26T15:01:40.313 回答
0

贪心算法建议是一种很好的启发式算法，但绝对不能保证给出最佳解决方案。这个问题是 NP 难的。它可以使用局部搜索（例如模拟退火）随机“解决” - 其中解决方案意味着“好”答案：一个被认为接近最优的答案。Knuth 提出了这个问题，对于 40 个权重和三个罐子，权重等于 1..40 的平方根。

格里

于 2013-06-26T19:13:25.980 回答