JS が貪欲アルゴリズムを使用して変更問題を解決する方法

現実の生活では、額面が 20、10、5、1 のコインが無制限にあると仮定します。 必要な小銭の量を考慮して、最小限のコインを使用することが要件となります。

この種の問題に対して、貪欲アルゴリズムは、両替時に常に両替可能なコインの最大値を選択する方法を採用しています。たとえば、必要な変更数が 25 の場合、変更方法は 10+10+5 ではなく 20+5 になります。

貪欲アルゴリズムは依然として最も一般的なアルゴリズムの 1 つであり、実装が簡単であり、貪欲戦略を構築するのがそれほど難しくないためです。この記事では、貪欲アルゴリズムを使用して変更の問題を解決する JS の例を共有します。

残念ながら、問題のアルゴリズムに実際に適用する前に、それを証明する必要があります。

<script>
 var money= [20,10,5,1];
 /*
  * m[]:存放可供找零的面值，降序排列
  * n:需要找零数
  */
 function greedyMoney(m,n){
  for(var i=0;i<m.length;i++){
    while(n>=m[i] && n>0){
    document.write(m[i]+" ");
    n = n-m[i];
    }
  }
  document.write("<br>");
  }
  greedyMoney(money,73);
  greedyMoney([25,10,1],63);
</script>

結果は次のとおりです:

20 20 20 10 1 1 1
25 25 10 1 1 1

場合によっては、変更問題に貪欲なアルゴリズムを使用すると全体的な最適解を取得できず、結果が最適解の適切な近似値のみです。

たとえば、提供されたおつりの額面が 11、5、1 の場合、おつりは 15 です。

貪欲アルゴリズムを使用した変更方法は 11+1+1+1+1 で、5 枚のコインが必要ですが、最適解は 5+5+5 で、3 枚のコインしか必要としません。

関連する推奨事項:

JS は最小限の変更シートを実装します

Python で実装された変更のための小さなプログラム コード

変更を見つける 2 つの方法

以上がJS が貪欲アルゴリズムを使用して変更問題を解決する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。