用Python暴力求解德·梅齐里亚克的砝码问题

问 一个商人有一个40磅的砝码，由于跌落在地而碎成4块。后来，称得每块碎片的重量都是整磅数，而且可以用这4 块来称从1 至40 磅之间的任意整数磅的重物。问这4 块砝码片各重多少？

这道题看上去其实不太靠谱，毕竟要用4个数组合出40种情况，看上去还是有些吃力的。因为，四个数的组合至多有$C_4^1+C_4^2+C_4^3+C_4^4=17$种情况。

考虑到用天平秤东西时，砝码可以放在天平两侧，这意味着两个砝码有2种称法；3个砝码最多有4种称法；4个砝码最多有6种称法，这样一来总共有46种称法，看来是合理的。

接下来考虑，将40拆分成4个数，共有多少种可能性，如果不删除重复，那就是$40\times 39\times 38\times 37$。

这样一来，这个问题的规模也就出来了，大概在$40^5$量级，直接暴力搜解就OK。

固定个数的砝码可称量重量

首先，创建一个函数，输入不同重量的砝码，然后得到可以称量的所有重量

from itertools import permutations
# 可以称出的所有重量
def allWeight(lst):
    ws = []
    N = len(lst)//2+1
    for L in permutations(lst):
        for i in range(N):
            w = abs(sum(L[:i])-sum(L[i:]))
            if w==0: continue
            ws.append(w)
    return set(ws)

随便拿几个数组测试一下

>>> allWeight([1,2])
{1, 3}
>>> allWeight([1,2,3])
{2, 4, 6}
>>> allWeight([1,2,3,4])
{2, 4, 6, 8, 10}

以1，2，3为例，1+2+3=6；1+3-2=2；2+3-1=4，故可称量2,4,6三种重量。

砝码的组合方法

接下来，考虑到可以用[1,2,3,4]中任意组合所能称出的所有重量，其方法在allWeight的基础上，需要加一个抽选的功能

import numpy as np
def allSubSet(lst):
    lst = np.array(lst)
    N = len(lst)
    subSet = []
    for i in product(*([[0,1]]*N)):
        if np.sum(i)==0:
            continue
        subSet.append(lst[np.array(i)==1])
    return subSet

接下来测试一下

>>> allSubSet([1,2,3])
[array([3]), array([2]), array([2, 3]), array([1]), array([1, 3]), array([1, 2]), array([1, 2, 3])]

40镑砝码的组合

题意要求40磅的砝码摔成了整数个，这个当然也能用组合来做，而且可以非常暴力，只需暴力搜索4个小于40个值，和为40就可以了。

parts = []
L40 = list(range(40))
for i in product(*([L40]*4)):
    if sum(i) == 40:
        parts.append(i)

最后得到总共有12337种组合。

最后，再对这12337种组合筛选就完事儿了

WS = set(range(1,41))
for L in parts:
    subLs = allSubSet(L)
    ws = set()
    for sub in subLs:
        ws.update(allWeight(sub))
    if ws == WS:
        print(sub)

最后输出了24个结果，无一列外都是[1,3,7,29]，这说明这个暴力穷举还是很低效的，可以考虑优化一下，速度能提高24倍。