算法簡介：

有一個貨幣系統(tǒng)，它有n種貨幣，它的面值為V1,V2,V3......... ,其中V1 =1。請?jiān)O(shè)計(jì)一動態(tài)規(guī)劃算法實(shí)現(xiàn)以最小的貨幣數(shù)目兌換面值為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("輸入硬幣種類的數(shù)目：");  
                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("兌換的最小硬幣的個數(shù)是：" +table[n][m]);  
                System.out.println("---------------------------------");  
            }  
        }  
      
    }  

標(biāo)簽： 代碼

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。