算法_动态规划_最少硬币问题

问题描述：
设有n 种不同面值的硬币，各硬币的面值存于数组T〔1:n〕中。现要用这些面值的硬
币来找钱。可以使用的各种面值的硬币个数存于数组Coins〔1:n〕中。
对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。
?编程任务：
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，
以及钱数m，0≤m≤20001，编程计算找钱m的最少硬币数。
?数据输入：
由文件input.txt 提供输入数据，文件的第一行中只有1 个整数给出n的值,第2 行起每
行2 个数，分别是T[j]和Coins[j]。最后1 行是要找的钱数m。
?结果输出:
程序运行结束时，将计算出的最少硬币数输出到文件output.txt中。问题无解时输出-1。
输入文件示例 输出文件示例
input3
1 3
2 3
5 3
18
output
5

import java.util.Scanner;

public class Main {
private static final int MAX=1000000; 
private static int n;
private static int m;
private static int[] T;
private static int[] Coins;
private static int[][] c;
private static boolean[][] hasUsed; 
/**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);

        n=sc.nextInt();
        T=new int[n+1];
        Coins=new int[n+1];
for(int i=1;i<=n;i++){
            T[i]=sc.nextInt();
            Coins[i]=sc.nextInt();
        }

        m=sc.nextInt();
        c=new int[n+1][m+1];
        hasUsed=new boolean[n+1][m+1];

for(int i=0;i<=n;i++){
            c[i][0]=0;
        }

for(int j=1;j<=m;j++){
            c[0][j]=MAX;
        }

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j-T[i]<0){
                    c[i][j]=c[i-1][j];
                    hasUsed[i][j]=false;
                }else if(c[i-1][j]<1+c[i][j-T[i]]){
                    c[i][j]=c[i-1][j];
                    hasUsed[i][j]=false;
                }else{
if(judge(i,j)){
                        c[i][j]=1+c[i][j-T[i]];
                        hasUsed[i][j]=true;
                    }else{
                        c[i][j]=c[i-1][j];
                        hasUsed[i][j]=false;
                    }
                }

            }
        }

if(c[n][m]>=MAX){
            System.out.println(-1);
        }else{
            System.out.println(c[n][m]);
        }


    }

private static boolean judge(int i,int j){
int sum=1;
        j-=T[i];
while(j>=1){
if(hasUsed[i][j]){
                sum++;
            }
            j-=T[i];
        }
if(sum>Coins[i]){
return false;
        }else{
return true;
        }
    }
}