最少硬币问题

- 日理万妓 2022-05-27 10:11 205阅读 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();
        }
    }