换钱最少货币数_python3
换钱的最少货币数
http://www.nowcoder.com/questionTerminal/4e05294fc5aa4d4fa8eacef2e606e5a8
暴力效率较低，而且需要循环计算知道找到有解的情况，下面只是个错误的例子
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
查看5道真题和解析