最小的石堆

Question

问题：您将得到一个整数权重列表。您需要将这些权重分配到两个集合中，以使每个集合的总权重之间的差异尽可能小。输入数据：权重列表。输出数据：一个数字，表示可能的最小重量差。我看到了一个答案，但我不明白为什么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 bestvaldef diff(a,b):    if a >= b:        return a - b    else:        return b - a

Answer 1

bestval最初只是设置为-1，并且第一次在循环中更新为d。此后，bestval每次都重新更新，d该值是比current更好的值（也就是较小的权重差）bestval。

关键代码在这里...

if bestval == -1 or d < bestval:

    bestval = d 

因此，在循环的第一遍中，它bestval == -1是正确的，并且会bestval被更新。之后，d < bestval检查将确定是否更新该值。

Answer 2

贪婪算法建议是一种很好的启发式方法，但绝对不能保证提供最佳解决方案。这个问题是NP难的。可以使用局部搜索（例如模拟退火）随机地“解决”该问题-解决方案表示“好”答案：一个被认为接近最佳答案的答案。克努斯（Knuth）提出了这个问题，适用于40个砝码和3个广口瓶，砝码等于1..40的平方根。