特定の金額を構成するコインの最適な組み合わせを見つける必要があります。だから本質的に、私はそこに到達するために最小限のコインを使用したいと思います。
例えば：
通貨システムにコインがある場合：{13、8、1}、貪欲なソリューションは24に対して{13、8、1、1、1}として変更されますが、真の最適なソリューションは{8、8、8}です。 。
私はこれをJavascriptで書きたいと思っていますが、より多くの人に役立つと確信しているので、擬似コードは問題ありません。
2 に答える
6
一般に、問題は実際にはNP完全です（変更を行う問題を参照）。ただし、多くの通貨システム（{1、5、10、25}の米国システムを含む）では、欲張りアルゴリズムも最適です。
于 2010-10-08T23:46:22.523 に答える
1
この問題は動的計画法を叫びます。
基本的な擬似コードは次のようになります。
- C（n）をnに合計するために使用されるコインの最小数とします。
- 各再帰ステップで、次の最大値のコインcを見つけ、 C（n）を次のように選択します。
- C（nc）+1（上記のコインを使用し、使用されたコインの合計と残りの値を更新する）とC（n） （コインを使用しない）の間の最小値-どちらの場合も、使用可能なコインリストからcを削除します次の反復。
このアルゴリズムは、参照している一般的なケースに適していることに注意してください。各コインが次のコインの約数である他のコインシステム（世界のほとんどのコインシステム）の場合、貪欲なソリューションが最も簡単で最適です。
于 2010-10-08T23:44:01.890 に答える