JavaScriptで蟻本 貪欲法 コインチェック

概要

アルゴリズムを学習をした際の記録を投稿します。
今回は蟻本・貪欲法のコインチェックについてです。

問題

以下引用

>1円玉、5円玉、10円玉、50円玉、100円玉、500円玉が、それぞれC1,C2,C10,C100,C500枚ずつあります
> できるだけ少ない枚数の効果でA円を支払いたいと考えています。
>何枚の効果を出す必要があるでしょうか？なお、その様な支払い方は少なくとも1つは存在するとします。

コード部分

/**  コインチェックpp43
 *
 * @param sum{Number} 金額の合計額
 * @param coinNumbers{Number} 各コインの枚数 要素数は6 1番目は1円、2番目は5円,3番目は10円,4番目は50円,5番目は100円,6番目は500円
 * @return {Number} コインの最小枚数
 */
const  check = (sum,coinNumbers) =>{
    const coinValue = [1,5,10,50,100,500];
    let ans = 0;
    let tempSum = sum;
    console.log(`貪欲法 コインチェック 状態遷移図`);
    console.log(`i|tempSum|ans`);
    console.log(`:--:|:---:|:-----:`);
    for(let i=5;i > 0; i--){
        let tempNumber = Math.min(Math.floor(tempSum/coinValue[i]),coinNumbers[i])
        tempSum -= tempNumber * coinValue[i]
        ans += tempNumber
        console.log(`${i} | ${tempSum} | ${ans}`);
    }
    return ans;
}

//硬貨の問題単体テスト 620円を満たす少ない硬貨の枚数。[1,5,10,50,100,500]円= [3,2,1,3,0,2]
// 結果値6
check(620,[3,2,1,3,0,2])

その他情報

一言

for文１個かつややこしい処理がないので、理解しやすかったです。

依存関係グラフ

依存関係グラフは変数の結びつきを一目でわかりやすくするための図です。
変数の流れを確認しやすくすることでワーキングメモリの負担を減らすことができます。
作成方法はコード上の変数に丸付けて線を繋げています。

状態遷移表

計算内容を明示する表。
ステップごとの変数の値を各列に表示します。
複雑な計算を行うコードを理解するのに役立つ表です。

i	tempSum	ans
5	120	1
4	120	1
3	20	3
2	10	4
1	0	6

python tutor

コードを実際に動かせるwebサイト
ステップ実行かつステップ事の変数を確認できる特徴があります。

リンク

参考資料

プログラミングコンテストチャレンジブック [第2版]　マイナビ　p42

プログラマー脳　秀和システム
p73 python tutor
p71 状態遷移表　
p69 依存関係グラフ

githubコミット部分