M28780: 零钱兑换3

http://cs101.openjudge.cn/practice/28780/

给定一组n种不同面额的硬币，以及要支付的总金额

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

输入

输入为两行

第一行为两个整数n（1 ≤ n ≤ 100），m（0 ≤ m ≤ 10^6），其中n表示硬币的种类数，m表示要凑的总金额

第二行为n个整数，表示硬币的面值

输出

可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，则输出 -1。

样例输入

sample1 input:
3 11
1 2 4

sample1 output:
4

样例输出

sample2 input:
1 3
2

sample2 output:
-1

提示

来源

2024 TA-Lhw

完全背包，类似于剪彩 189A. Cut Ribbon，https://codeforces.com/problemset/problem/189/A

时间：16875ms

python

n, m = map(int, input().split())
coins = list(map(int, input().split()))
dp = [float("inf")] * (m + 1)
dp[0] = 1
for i in coins:
    dp[i] = 1
for i in range(1, m + 1):
    for coin in coins:
        if i - coin >= 0:
            dp[i] = min(dp[i], dp[i - coin] + 1)

#print(dp)
if dp[m] == float("inf"):
    print(-1)
else:
    print(dp[m])

python

from math import inf
n, m = map(int, input().split())
coins = list(map(int, input().split()))
dp = [0] + [inf for _ in range(m)]
for i in range(n):
    for j in range(coins[i], m + 1):
        dp[j] = min(dp[j], dp[j - coins[i]] + 1)
print(dp[m] if dp[m] != inf else -1)

时间：5210ms

python

# 2400010989	韩宇宸 工学院
import bisect

# 读取输入
n, m = map(int, input().split())
face = sorted(map(int, input().split()))  # 直接排序后使用
coins = [float('inf')] * (m + 1)
coins[0] = 0  # 初始值

# 动态规划计算最小硬币数
for i in range(1, m + 1):
    w = bisect.bisect_right(face, i)

    #for k in range(w):
    #    coins[i] = min(coins[i], coins[i - face[k]] + 1)
    if w != 0:
        coins[i] = min(coins[i - face[k]] for k in range(w)) + 1

# 输出结果
print(coins[m] if coins[m] != float('inf') else -1)

M28780: 零钱兑换3 ​

M28780: 零钱兑换3