题目链接

硬币凑钱

题目描述

银行拥有面值为1元、5元与7元的硬币若干,每种面值的硬币数量均视为无限。现在需要支付恰好 元,求出所需硬币数量的最小值。

解题思路

这是一个典型的“完全背包”求最优解的问题。我们可以使用动态规划来求解。

我们定义一个一维数组 ,其中 表示凑成总金额为 所需的最少硬币数量。我们的目标是求

首先,初始化 数组。,因为凑成金额0需要0个硬币。对于其他金额 ,我们应该将 初始化为一个非常大的数(表示无穷大),代表当前还无法凑成该金额。

然后,我们遍历每一种硬币。对于面值为 的硬币(这里是1, 5, 7),我们来更新 数组。对于一个金额 (从 ),凑成它的方法可以是在凑成 的基础上,再加一枚面值为 的硬币。此时,总硬币数为 。我们需要在所有可能性中取最小值。

由此,我们可以得到状态转移方程:

这个方程的含义是:凑成金额 所需的最少硬币数,是当前已知的 和 “凑成 的最少硬币数再加1” 这两者中的较小值。

完整的算法流程如下:

  1. 创建一个大小为 的数组 ,并将 初始化为0,其余初始化为无穷大。
  2. 定义硬币面值数组 coins = {1, 5, 7}
  3. 对于每一种硬币 v in coins
  4. 对于从 v 的每一个金额
  5.  更新 $dp[j] = \min(dp[j], dp[j - v] + 1)$。
    
  6. 遍历完所有硬币后, 就是最终的答案。

代码

#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 数组。