python - 用 Python 解决难题

Question

我有一个难题，我想用 Python 解决它。

Puzzle:

A merchant has a 40 kg weight which he used in his shop. Once, it fell from his hands and was broken into 4 pieces. But surprisingly, now he can weigh any weight between 1 kg to 40 kg with the combination of these 4 pieces.

So question is, what are weights of those 4 pieces?

现在我想用 Python 解决这个问题。

我从拼图中得到的唯一限制是 4 block 的总和是 40。这样我可以过滤所有总和为 40 的 4 个值的集合。

import itertools as it

weight = 40
full = range(1,41)
comb = [x for x in it.combinations(full,4) if sum(x)==40]

梳子长度 = 297

现在我需要检查comb中的每一组值，并尝试所有的操作组合。

例如如果(a,b,c,d)是comb中的第一组值，我需要检查a,b,c， d,a+b,a-b, ........a+b+c-d,a-b+c+d........等等。

我尝试了很多，但我被困在这个阶段，即如何检查所有这些计算组合到每组 4 个值。

问题:

1) 我想我需要列出 [a,b,c,d] 和 [+,-] 的所有可能组合。

2) 有没有人有更好的主意并告诉我如何从这里继续前进？

另外，我想完全不需要任何外部库的帮助，只需要使用 python 的标准库。

编辑:抱歉信息迟到了。它的答案是 (1,3,9,27)，这是我几年前发现的。我已经检查并验证了答案。

编辑:目前，fraxel 的答案完美适用于 time = 0.16 ms。更好更快的方法总是受欢迎的。

问候

方舟

Answer 1

之前的演练答案:

我们知道 a*A + b*B + c*C + d*D = x 对于 0 到 40 之间的所有 x 和 a， b, c, d 仅限于 -1, 0, 1。显然 A + B + C + D = 40。下一种情况是 x = 39，因此显然最小的移动是删除一个元素(这是唯一可能导致成功平衡 39 的移动):

A + B + C = 39，所以 D = 1，根据需要。

下一个:

A + B + C - D = 38

下一个:

A + B + D = 37，所以 C = 3

然后:

A + B = 36

然后:

A + B - D = 35

A + B - C + D = 34

A + B - C = 33

A + B - C - D = 32

A + C + D = 31，所以 A = 9

因此B = 27

所以权重是1,3,9,27

实际上，这可以从它们都必须是 3 的倍数这一事实中立即推断出来。

有趣的更新:

所以这里有一些 Python 代码，可以为任何跨越空间的掉落重量找到最小的重量集:

def find_weights(W):
    weights = []
    i = 0
    while sum(weights) < W:
        weights.append(3 ** i)
        i += 1
    weights.pop()
    weights.append(W - sum(weights))
    return weights

print find_weights(40)
#output:
[1, 3, 9, 27]

为了进一步说明这一解释，可以将问题视为跨越数字空间 [0, 40] 的最小权重数。很明显，每个重量可以做的事情是三元/三元(增加重量，去除重量，把重量放在另一边)。因此，如果我们按降序编写(未知)权重(A, B, C, D)，我们的 Action 可以总结为:

    ABCD:   Ternary:
40: ++++     0000
39: +++0     0001
38: +++-     0002
37: ++0+     0010
36: ++00     0011
35: ++0-     0012
34: ++-+     0020
33: ++-0     0021
32: ++--     0022
31: +0++     0100
etc.

我把从 0 到 9 的三进制数放在旁边，以说明我们实际上是在一个三进制数系统中(以 3 为底)。我们的解决方案总是可以写成:

3**0 + 3**1 +3**2 +...+ 3**N >= Weight

对于这个成立的最小 N。最小的解决方案总是这种形式。

此外，我们可以轻松解决大权重问题并找到跨越空间的最小块数:

一个人掉下一个已知重量 W，它碎成碎片。他的新砝码允许他称重最大为 W 的任何重量。有多少个砝码，它们是什么？

#what if the dropped weight was a million Kg:
print find_weights(1000000)
#output:
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 202839]

尝试对大重量和未知数量的碎片使用排列!