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 回答