Posts pythonTip 48 砝码问题II
Post
Cancel

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()

This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 47 杨辉三角

pythonTip 49 进制转换

Trending Tags