算法_動態規劃_貨幣兌換

算法簡介：

有一個貨幣系統，它有n種貨幣，它的面值為V1,V2,V3......... ,其中V1 =1。請設計一動態規劃算法實現以最小的貨幣數目兌換面值為m 的錢。

代碼如下：

    import java.util.Scanner;


public class Algorithm_2 {  

    /** 
     * @param args 
     */  
    private static final int MAX_M=20;  
    private static final int MAX_N=100000;  
    private static int[][] table = new int[MAX_N][MAX_M];  
    private static int[] value = new int[MAX_N];  

    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  
        while(true){  
            System.out.println("輸入硬幣種類的數目：");  
            int m = sc.nextInt();  
            System.out.println("從小到大輸入硬幣的面值，其中第一個是1：");  

            for(int i=1;i<=m;i++)  
                value[i]= sc.nextInt();  
            System.out.println("輸入要兌換的錢的面值：");  
            int n = sc.nextInt();  

            for(int i=0;i<=n;i++)//初始化  
                table[i][0]=0;  
            for(int i=0;i<=m;i++)  
                table[0][i]=0;  

            for(int i=1;i<=n;i++){  
                for(int j=1;j<=m;j++){  
                    if(value[j] == i)  
                        table[i][j]=1;  
                    else if(value[j]<i)  
                        table[i][j]=table[i-value[j]][j]+1;  
                    else table[i][j]=table[i][j-1];  
                }  
            }  
            System.out.println("兌換的最小硬幣的個數是：" +table[n][m]);  
            System.out.println("---------------------------------");  
        }  
    }  

}  </pre>