换钱最少货币数_python3

暴力效率较低，而且需要循环计算知道找到有解的情况，下面只是个错误的例子

def solve(l, n, k):
    if n < 1:
        return 0
    count = 0
    for i in l:
        count += k//i
        k %= i
        if not k:
            break
    return count if not k else -1

while True:
    try:
        n, k = map(int, input().split())
        l = list(map(int, input().split()))
        l = sorted(l, reverse=True)
        print(solve(l, n, k))
    except EOFError:
        break

动态规划，背包九讲有详细描述，与传统的背包本质是一样的，每件物品的价值和容量正好对应货币值和1，固定容量与固定总货币值，需要注意装满的情况初始化只有第0个状态有效，求最小初始化用最大值且用min，反之反之，排不排序都可以

MAX = 1001
def solve(l, n, k):
    c = [MAX]*(k+1)
    c[0] = 0
    for i in range(n):
        for v in range(l[i], k+1):
            c[v] = min(c[v], c[v-l[i]]+1)
    return c[k] if c[k] != MAX else -1

while True:
    try:
        n, k = map(int, input().split())
        l = list(map(int, input().split()))
        print(solve(l, n, k))
    except EOFError:
        break