JAvaダイナミックプランニングアルゴリズム-コインのお釣り問題の例分析

この例ではjavaダイナミックプランニングアルゴリズムであるコインのお釣り問題について説明します.皆さんの参考にしてください.具体的には以下の通りです.
問題の説明
今3種類の硬貨があります:1元、5元、10元、今あなたに63元をあげて、あなたにすべて硬貨に変えさせて、最小の硬貨の数量を求めて、つまり、どのように最小の硬貨の数で63元を集めます.
問題を分析する
この問題を解決するには、この大きな問題をいくつかの小さな問題に分けて、下から上へ問題を解決することができます.
1元に対応する最小硬貨数は1です
2元に対応する最小硬貨数は2
3元に対応する最小硬貨数は3
4元に対応する最小硬貨数は4です
……
63元対応の最小硬貨数はXXX
先に計算した金額に対応する最小硬貨数をメモのように記録しておくと、後の金額に対応する最小硬貨数の方が言いやすいのはなぜですか?
例:63の最小硬貨数を要求すると、63-1=62、63-5=58、63-10=53と計算する必要があります.62、58、53に対応する最小硬貨数がメモ配列に記録されていると仮定します.このとき、62、58、53の中で誰が対応する最小硬貨数が最小なのかを見つけて、1を加えると、63の対応する最小硬貨数になります.63は62,58,53よりも大きいので,最良の場合は62,58,53の中で最小の1つを見つけることにほかならないが,これが最適解である.
このような覚書思想に基づいて、私たちはプログラミングを行います.まず、処理するデータを配列と必要なパラメータに変換します.

int[] coins = { 1 , 5 , 10 }; //      
int adm = 63; //     
int[] money = new int[63+1]; //    ，        

説明:money配列はメモ配列であり、例えばmoney[0]が0、money[1]が1、money[2]が2…
次に、私たちの上の解題の構想を抽象的に関数にして、関数の中でただ:循環、判断、賦値......どのようにこれらの論理文を利用して、私たちの構想を説明して、これは最も難しいで、水が漏れないようにするため、状況はすべて周到に考えなければならなくて、1歩の結果は間違って、これは長い間抽象的な論理の思考を鍛える必要があります.私の比較的に習慣的な方法はコードを見ながら、問題の構想を関連付けて、それから真似して、コードの中に注釈があって、みんなは見ながら分析しましょう:

public static void main(String[] args) {
 
 int[] coins = {1,5,10};
 int money = 63;
 
 changeMoney(coins,money);
}
 
/**
 *       ,     
 * @param coins        
 * @param money     
 */
public static void changeMoney( int[] coins , int money ) {
 //     ，    
 int[] memo = new int[money + 1];
 //0          0
 memo[0] = 0;
 
 System.out.println( "  \t" + "        " );
 //       ，              ，   1   
 for( int currentMoney = 1 ; currentMoney <= money ; currentMoney++ ) {
 //                
 //  ：63     63 1     
 int minCoins = currentMoney;
 //        ，               1
 for( int coinKind = 0 ; coinKind < coins.length ; coinKind++ ) {
 //                           
      //  ：5-1=4,5-5=0,5-10=-5，    -5   ……
 if( currentMoney >= coins[coinKind] ) {
 //                      
 //             1
 int tempCoins = memo[currentMoney - coins[coinKind]] + 1;
 //             
 //  ：63  tempConis 
 //   memo[63-1]+1、memo[63-5]+1、memo[63-10]+1
 //        
 if( tempCoins < minCoins ) {
  minCoins = tempCoins;
 }
 }
 }
 //              ，           
 memo[currentMoney] = minCoins;
 
 System.out.println( currentMoney + "\t" + memo[currentMoney] );
 }
}

実行結果
金額に対応する最小硬貨数1 1 2 3 3 4 4 5 1 6 2 7 3 8 4 9 5 10 1 11 2 3 13 4 4 4 4 4 4 5 4 6 2 7 3 8 4 9 5 10 1 11 2 3 3 13 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 17     4 18        5 19        6 20        2 21        3 22        4 23        5 24        6 25        3 26        4 27        5 28        6 29        7 30        3 31        4 32        5 33        6 34        7 35        4 36        5 37        6 38        7 39        8 40        4 41        5 42        6 43        7 44        8 45        5 46        6 47        7 48        8 49        9 50        5 51        6 52        7 53        8 54        9 55        6 56        7 57        8 58        9 59        10 60        6 61        7 62        8 63        9
Javaアルゴリズムに関する詳細に興味のある方は、「Javaデータ構造とアルゴリズムチュートリアル」、「Java操作DOMノードテクニックまとめ」、「Javaファイルとディレクトリ操作テクニックまとめ」、「Javaキャッシュ操作テクニックまとめ」のトピックを参照してください.
本文で述べたjavaプログラム設計に役立つことを願っています.