最少硬币问题-蒲公英云

最少硬币问题

- 日理万妓 2022-05-27 10:11 289阅读 0赞

最少硬币问题
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。
对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，计算找钱m的最少硬币数。
Input
输入数据第一行中只有1个整数给出n的值,第2行起每行2个数，分别是T[j]和Coins[j]。最后1行是要找的钱数m。
Output
输出数据只有一个整数，表示计算出的最少硬币数。问题无解时输出-1。
Sample Input
3
1 3
2 3
5 3
18
Sample Output
5
Hint

Source

import java.util.*;
class Main {
    static int min(int a, int b) {
        return a < b ? a : b;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner ss = new Scanner(System.in);
        int n;
        final int mm = 20001;
        final int coinnum = 15;
        int dp[];
        int coin[];
        int coinn[];
        n = ss.nextInt();
        dp = new int[mm + 1];
        coin = new int[coinnum];
        coinn = new int[coinnum];
        for (int i = 1; i <= mm; i++) {
            dp[i] = mm;
        }
        for (int i = 0; i < n; i++) {
            coin[i] = ss.nextInt();
            coinn[i] = ss.nextInt();
        }
        int m;
        m = ss.nextInt();
        int i, j, k;
        for (i = 0; i < n; i++) {
            for (j = 0; j < coinn[i]; j++) {
                for (k = m; k >= coin[i]; k--) {
                    dp[k] = min(dp[k - coin[i]] + 1, dp[k]);
                }
            }
        }
        if (dp[m] == mm)
            System.out.println(-1);
        else
            System.out.println(dp[m]);
        ss.close();
    }
}