技術文章 » 拼湊硬幣問題

拼湊硬幣問題

2022-11-03 15:01:26

拼湊硬幣問題

作者：Grey

原文地址：

部落格園：拼湊硬幣問題

CSDN：拼湊硬幣問題

問題描述

現有 n1 + n2 種面值的硬幣，其中前 n1 種為普通幣，可以取任意枚，後 n2 種為紀念幣， 每種最多隻能取一枚（可能有重複值），每種硬幣有一個面值，問能用多少種方法拼出 m 的面值?

題目連結見：牛客-拼湊硬幣

主要思路

如果都用普通幣，組合出 m 有多少種方法？假設得到 x 種方法。

如果都用紀念幣，組合出 m 有多少種方法？假設得到 y 種方法。

如果是普通幣 + 紀念幣，組合出 m 有多少種方法？ 假設得到 z 種方法。

則 x + y + z 就是結果。

所以需要定義兩個遞迴函數。

第一個遞迴函數：用紀念幣，組成不同錢數的組合數量有多少

long[][] one(int[] arr, int money)

遞迴含義表示：用紀念幣，返回組成不同錢數的組合數量有多少。由於紀念幣每種最多隻能選一個，所以這是一個經典的揹包問題。

注：這個遞迴返回的是一個二維陣列 dp，dp[i][j]表示 0 號到 i 號紀念幣任意選擇的情況下，組合出 m 有多少種方法。

遞迴含義確定後，二維陣列 dp 的第 0 列的值已經可以很快確定，因為 dp[i][0] 表示 0 號到 i 號紀念幣任意選擇的情況下，組成 0 面值有多少方法。

顯然只有一種方法，就是什麼都不選，即

for (int i = 0; i < arr.length; i++) {
    dp[i][0] = 1;
}

dp[0][arr[0]] 的值也可以確定，因為 dp[0][arr[0]] 表示：0 號面值的紀念幣，如何組成arr[0] 的面值，顯然只有一種方法，就是選 0 號的面值，但是需要滿足一個條件，即 arr[0] <= money，即

if (arr[0] <= money) {
    dp[0][arr[0]] = 1;
}

接下來就是普遍情況，對於任意 dp[i][j] 來說，首先可以有一種決策，不要 i 位置的紀念幣，即

dp[i][j] = dp[i-1][j]

第二種決策，就是使用 i 位置的一枚紀念幣，此時，要滿足前提條件，即 arr[i] 位置的面值不能超過剩餘面值

即：

dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;

遞迴函數的完整程式碼如下

    public static long[][] one(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= money) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }

第二個遞迴函數：用普通幣，組成不同錢數的組合數量有多少

long[][] many(int[] arr, int money)

遞迴含義表示：用普通幣，組成不同錢數的組合數量有多少。也是返回一個二維陣列 dp，dp[i][j]表示 0 號到 i 號普通幣任意選擇的情況下，組合出 m 有多少種方法。

根據遞迴含義，二維陣列 dp 的第 0 列的值全為 1， 組成 0 面值的組合只有一種情況，就是用 0 枚普通幣。即

for (int i = 0; i < arr.length; i++) {
    dp[i][0] = 1;
}

第 0 行也比較好確認，就是列舉 arr[0] 最多可以使用多少枚，即

for (int j = 1; arr[0] * j <= money; j++) {
    dp[0][arr[0] * j] = 1;
}

接下來是普遍位置，dp[i][j] 有兩個決策，第一個決策，不使用 i 位置的普通幣，即

dp[i][j] = dp[i-1][j]

第二個決策，使用 i 位置的普通幣，此時，要滿足前提條件，即 arr[i] 位置的面值不能超過剩餘面值
即：

dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;

所以，遞迴函數的完整程式碼如下

    public static long[][] many(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; arr[0] * j <= money; j++) {
            dp[0][arr[0] * j] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }

整合函數，普通幣和紀念幣一起使用

有了上述兩個 dp ，就可以很方便計算兩種硬幣一起使用過程的組合數量，核心思路就是這句

dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i];

即：只用 普通幣完成 i 面值的組合數量是 M，用紀念幣完成 money - i 面值的組合數量是 N，則 M * N 就是兩者一起用組合成 money 面值的組合數量。

這個整合函數的完整程式碼如下


    public static long moneyWays(int[] many, int[] one, int money) {
        if (money < 0) {
            return 0;
        }
        if ((many == null || many.length == 0) && (one == null || one.length == 0)) {
            return money == 0 ? 1 : 0;
        }
        long[][] dpMany = many(many, money);
        long[][] dpOne = one(one, money);
        if (dpMany == null) {
            return dpOne[dpOne.length - 1][money];
        }
        if (dpOne == null) {
            return dpMany[dpMany.length - 1][money];
        }
        long res = 0;
        for (int i = 0; i <= money; i++) {
            res += dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i];
            res %= MOD;
        }
        return res;
    }

完整程式碼

import java.util.Scanner;

public class Main {
    static int MOD = (int) 1e9 + 7;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n1 = in.nextInt();
        int n2 = in.nextInt();
        int target = in.nextInt();
        int[] many = new int[n1];
        int[] one = new int[n2];
        for (int i = 0; i < n1; i++) {
            many[i] = Integer.parseInt(in.next());
        }
        for (int i = 0; i < n2; i++) {
            one[i] = Integer.parseInt(in.next());
        }
        System.out.println(moneyWays(many, one, target));
        in.close();
    }

    public static long moneyWays(int[] many, int[] one, int money) {
        if (money < 0) {
            return 0;
        }
        if ((many == null || many.length == 0) && (one == null || one.length == 0)) {
            return money == 0 ? 1 : 0;
        }
        long[][] dpMany = many(many, money);
        long[][] dpOne = one(one, money);
        if (dpMany == null) {
            return dpOne[dpOne.length - 1][money];
        }
        if (dpOne == null) {
            return dpMany[dpMany.length - 1][money];
        }
        long res = 0;
        for (int i = 0; i <= money; i++) {
            res += dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i];
            res %= MOD;
        }
        return res;
    }

    public static long[][] many(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; arr[0] * j <= money; j++) {
            dp[0][arr[0] * j] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }

    public static long[][] one(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= money) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }
}

更多

演演算法和資料結構筆記