java如何實現硬幣求和

Java如何實現硬幣求和

在編程中，硬幣求和問題是一個經典的算法問題。假設我們有一組不同面額的硬幣，目標是找出這些硬幣的組合，使其總和等于給定的金額。本文將介紹如何使用Java實現這一功能。

問題描述

假設我們有一組硬幣，面額分別為1元、2元、5元、10元等。給定一個目標金額，例如11元，我們需要找出所有可能的硬幣組合，使得這些硬幣的總和等于11元。

動態規劃解決方案

動態規劃是解決硬幣求和問題的常用方法。我們可以使用一個數組dp來存儲達到每個金額所需的最少硬幣數。dp[i]表示達到金額i所需的最少硬幣數。

實現步驟

1. 初始化數組：創建一個大小為amount + 1的數組dp，并將所有元素初始化為Integer.MAX_VALUE，表示初始狀態下無法達到該金額。dp[0]初始化為0，因為金額為0時不需要任何硬幣。

2. 填充數組：遍歷每個金額i，從1到amount。對于每個金額i，遍歷每個硬幣面額coin，如果coin小于等于i，則更新dp[i]為dp[i]和dp[i - coin] + 1中的較小值。

3. 返回結果：最終，dp[amount]將包含達到目標金額所需的最少硬幣數。如果dp[amount]仍為Integer.MAX_VALUE，則表示無法達到該金額。

代碼實現

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println("最少需要的硬幣數: " + coinChange(coins, amount));
    }
}

運行結果

對于硬幣面額為[1, 2, 5]，目標金額為11元的情況，程序將輸出：

最少需要的硬幣數: 3

總結

通過動態規劃方法，我們可以有效地解決硬幣求和問題。該方法不僅適用于最少硬幣數的問題，還可以擴展到其他類似的組合優化問題。希望本文能幫助你理解如何在Java中實現硬幣求和。