pythonTip 48 砝码问题II

题目描述： 有一组砝码，重量互不相等，分别为m1、m2、m3……mn；每种砝码的数量有无限个。 现要用这些砝码去称物体的重量,给你一个重量n,请你判断有给定的砝码能否称出重量n。 现在给你一个正整数列表w和一个正整数n，列表w中的第i个元素w[i]表示第i种砝码的重量，n表示要你判断的重量。如果给定砝码能称出重量n，输出Yes，否则输出No。例如，w=[2,5,11], n=9,则输出Yes（取两个2，一个5）。

示例：

输入：w = [1, 2] n = 18 输出：Yes

分析:

给定一组重量不相等的砝码，每种砝码有无限个，然后现在要用这些砝码去称物体的重量n。让你去判断能否称出指定的重量，问题呢，就是这样的一个问题。

分析一下：

1. 如果当前物体重量n, 刚好是某一个砝码重量m[i]的倍数，那么有解。
2. 如果当前物体重量n, 小于最轻的一个砝码重量，那么无解。

现在我们确定了两种可以肯定是否有解的情况。 剩下的最后一种就是： 当前物体重量大于最轻的一个砝码重量，然后又不是其中某一个砝码重量的倍数。

对于这个问题怎么破解？

以我的能力，我只能确定到前面两种情况，对于最后一种情况，我是没有想到解决办法的，于是我百度了一下。

大佬的办法：

用当前物体重量减去最轻一个砝码的重量，依次循环，直到出现上面两种必然的情况时退出。

我乍的一想，秒啊，但是又无法证明。

假设 有 3 个砝码，重量依次为 a, b, c。 如果当前重量为 n = a + b * i + c * j。那么我要如何证明，上面依次循环是正确的？

我没有想到证明的方式。但我还是把代码贴出来吧。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

w.sort()

def main():
    global w, n
    while True:
        for v in w:
            if n % v == 0:
                print("Yes")
                return 

        n -= w[0]

        if n < w[0]:
            print("No")
            return 
main()