最小石桩
最小石桩
提问于 2013-06-26 22:40:45
问题：
您将看到一个整数权重列表。您需要将这些权重分配到两个集合中，以便每个集合的总权重之间的差异尽可能小。
输入数据:权重列表。
输出数据:一个数字，表示可能的最小权重差异。
我看到了答案，但我不明白为什么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
Stack Overflow用户
回答已采纳
发布于 2013-06-26 22:46:07
bestval最初设置为-1，并在第一次循环中更新为d。在此之后，每当d是比当前bestval更好的值(也称为更小的权重差异)时，bestval将再次更新。
关键代码在这里。
if bestval == -1 or d < bestval:
bestval = d 因此，在循环的第一次传递中，bestval == -1为true，并且更新了bestval。之后，d < bestval检查确定是否更新值。
Stack Overflow用户
发布于 2013-06-26 22:45:38
这是一个起始值，you know不可能是对的，所以无论多么糟糕，它都会被第一个答案所取代！
Stack Overflow用户
发布于 2013-06-26 23:01:40
我怀疑，经历所有的组合是一种解决问题的蛮力和缓慢的方法。
将权重按大小排序，然后从最重到最轻，根据桩之间的重量差异将它们逐个添加到左侧或右侧，可能会给出最佳答案。
下面的伪代码，使其成为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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17323218
复制相关文章
相似问题
腾讯云开发者
