用Python暴力求解德·梅齐里亚克的砝码问题
文章目录
- 固定个数的砝码可称量重量
- 砝码的组合方法
- 40镑砝码的组合
问 一个商人有一个40磅的砝码，由于跌落在地而碎成4块。后来，称得每块碎片的重量都是整磅数，而且可以用这4 块来称从1 至40 磅之间的任意整数磅的重物。问这4 块砝码片各重多少？
这道题看上去其实不太靠谱，毕竟要用4个数组合出40种情况，看上去还是有些吃力的。因为，四个数的组合至多有C41+C42+C43+C44=17C_4^1+C_4^2+C_4^3+C_4^4=17C41+C42+C43+C44=17种情况。
考虑到用天平秤东西时，砝码可以放在天平两侧，这意味着两个砝码有2种称法；3个砝码最多有4种称法；4个砝码最多有6种称法，这样一来总共有46种称法，看来是合理的。
接下来考虑，将40拆分成4个数，共有多少种可能性，如果不删除重复，那就是40×39×38×3740\times39\times38\times3740×39×38×37。
这样一来，这个问题的规模也就出来了，大概在40540^5405量级，直接暴力搜解就OK。
固定个数的砝码可称量重量
首先，创建一个函数，输入不同重量的砝码，然后得到可以称量的所有重量
from itertools import permutations
# 可以称出的所有重量
def allWeight(lst):ws = []N = len(lst)//2+1for L in permutations(lst):for i in range(N):w = abs(sum(L[:i])-sum(L[i:]))if w==0: continuews.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:continuesubSet.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倍。