题目链接
题目描述
银行拥有面值为1元、5元与7元的硬币若干,每种面值的硬币数量均视为无限。现在需要支付恰好 元,求出所需硬币数量的最小值。
解题思路
这是一个典型的“完全背包”求最优解的问题。我们可以使用动态规划来求解。
我们定义一个一维数组 ,其中
表示凑成总金额为
所需的最少硬币数量。我们的目标是求
。
首先,初始化 数组。
,因为凑成金额0需要0个硬币。对于其他金额
,我们应该将
初始化为一个非常大的数(表示无穷大),代表当前还无法凑成该金额。
然后,我们遍历每一种硬币。对于面值为 的硬币(这里是1, 5, 7),我们来更新
数组。对于一个金额
(从
到
),凑成它的方法可以是在凑成
的基础上,再加一枚面值为
的硬币。此时,总硬币数为
。我们需要在所有可能性中取最小值。
由此,我们可以得到状态转移方程:
这个方程的含义是:凑成金额 所需的最少硬币数,是当前已知的
和 “凑成
的最少硬币数再加1” 这两者中的较小值。
完整的算法流程如下:
- 创建一个大小为
的数组
,并将
初始化为0,其余初始化为无穷大。
- 定义硬币面值数组
coins = {1, 5, 7}
。 - 对于每一种硬币
v
incoins
: - 对于从
v
到的每一个金额
:
-
更新 $dp[j] = \min(dp[j], dp[j - v] + 1)$。
- 遍历完所有硬币后,
就是最终的答案。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9; // 代表无穷大
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int s;
cin >> s;
vector<int> coins = {1, 5, 7};
vector<int> dp(s + 1, INF);
dp[0] = 0;
// 遍历每种硬币
for (int coin : coins) {
// 遍历背包容量(金额)
for (int j = coin; j <= s; ++j) {
if (dp[j - coin] != INF) { // 确保 j-coin 是可达的
dp[j] = min(dp[j], dp[j - coin] + 1);
}
}
}
cout << dp[s] << "\n";
return 0;
}
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int s = sc.nextInt();
int[] coins = {1, 5, 7};
int[] dp = new int[s + 1];
final int INF = 1_000_000_000; // 代表无穷大
Arrays.fill(dp, INF);
dp[0] = 0;
// 遍历每种硬币
for (int coin : coins) {
// 遍历背包容量(金额)
for (int j = coin; j <= s; j++) {
if (dp[j - coin] != INF) { // 确保 j-coin 是可达的
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
}
System.out.println(dp[s]);
}
}
def solve():
s = int(input())
coins = [1, 5, 7]
INF = float('inf')
dp = [INF] * (s + 1)
dp[0] = 0
# 遍历每种硬币
for coin in coins:
# 遍历背包容量(金额)
for j in range(coin, s + 1):
if dp[j - coin] != INF:
dp[j] = min(dp[j], dp[j - coin] + 1)
print(dp[s])
solve()
算法及复杂度
- 算法:动态规划(完全背包求最优解)
- 时间复杂度:
,其中
是硬币种数(本题为常数3),
是目标金额。因此复杂度为
。
- 空间复杂度:
,用于存储
dp
数组。