习题3 找零钱给定硬币种类的个数，不同种类硬币的面额和一个总金额。请计算可以凑成总金额所需的最少的硬币个数 

习题3
找零钱给定硬币种类的个数，不同种类硬币的面额和一个总金额。请计算可以凑成总金额所需的最少的硬币个数。
样例1输入：3
1 2 5
11
样例1输出：3
样例2输入：2
1 3
2
样例2输出：2
样例3输入：5
1 5 18 45 78
233
样例3输出:7
样例4输入：10
3 0 10 24 98 37 12 38 76 32
777
样例4输出：9 

def solution(s:int,lst:list[int],s1:int):
    lst.sort()
    m=lst.count(0)
    if m>0:
        for j in range(m):
            lst.remove(0)
    x=len(lst)-1
    i=0
    if s1 in lst:
        return 1
    else:
        while x>=0:
            if s1/lst[x]>=1:
                m=int(s1/lst[x])
                
                i+=m
                s1=s1-m*lst[x]
                x-=1
            else:
                x-=1
    return i
print(solution(3,[1,2,5],11))

望采纳

img