最小的石堆

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 bestval

def 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:&nbsp; &nbsp; bestval = d&nbsp;因此，在循环的第一遍中，它bestval == -1是正确的，并且会bestval被更新。之后，d < bestval检查将确定是否更新该值。

Answer 2

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