在Python中解决难题

Question

我有一个谜题,我想用Python解决它.

难题:

一个商人的重量为40公斤,他在他的店里使用.有一次,它从他的手上掉下来,分成4块.但令人惊讶的是,现在他可以通过这4件的组合称重1公斤到40公斤之间的任何重量.

所以问题是,这4件的重量是多少？

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

我从拼图中得到的唯一约束是4个总和是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]

length of comb = 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] and [+,-].

2)有没有人有更好的想法,告诉我如何从这里前进？

另外,我想完全没有任何外部库的帮助,只需要使用python的标准库.

编辑:对不起,迟到的信息.答案是(1,3,9,27),这是我几年前发现的.我检查并验证了答案.

编辑:目前,fraxel答案是完美的time = 0.16 ms.总是欢迎更好,更快的方法.

问候

方舟

Answer 1

早期的演练anwswer:

我们知道a*A + b*B + c*C + d*D = x所有人都x在0到40之间,并且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)按降序编写我们的(未知)权重,我们的行动可以概括为:

    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]

尝试使用排列重量大,数量不详的!!

Answer 2

这是一个蛮力的itertools解决方案:

import itertools as it

def merchant_puzzle(weight, pieces):
    full = range(1, weight+1)
    all_nums = set(full)
    comb = [x for x in it.combinations(full, pieces) if sum(x)==weight]
    funcs = (lambda x: 0, lambda x: x, lambda x: -x)
    for c in comb:
        sums = set()
        for fmap in it.product(funcs, repeat=pieces):
            s = sum(f(x) for x, f in zip(c, fmap))
            if s > 0:
                sums.add(s)
                if sums == all_nums:
                    return c

>>> merchant_puzzle(40, 4)
(1, 3, 9, 27)

有关它是如何工作的解释,请查看Avaris给出的答案,这是同一算法的实现.