3

コインのセットが与えられた場合、可能な限り最適な方法で特定の金額に到達するにはどうすればよいでしょうか?

この場合、1、5、10、20、50 セントのコインの乱数があり、最大のコインが優先されるとします。

私の最初の直感は、収まる最大のコインをすべて使用し、合計を超えた場合は次に小さいコインを使い切るというものです。

これでうまくいきますか、それともこのアプローチに何か欠点がありますか? より効率的なアプローチはありますか?

4

3 に答える 3

8

最初に最大のコインを配るだけでは不十分です。

自動販売機が 50c、20c、1c の各 20 枚を除くすべてのコインを使い果たし、60c の釣り銭を提供する必要があるとします。

「最大優先」（または貪欲）方式では、11 枚のコイン、1 枚の 50c コイン、10 枚の 1c コインが得られます。

より良い解決策は、3 枚の 20c コインです。

貪欲なスキームは、局所的な最適解のみを提供します。グローバルな最適化の場合、通常はすべての可能性を調べて (検索スペースを減らすためのミニマックス タイプのアルゴリズムが存在する場合もあります)、変更を提供するために通常は計算可能性の範囲内にあることを確認する必要があります。

于 2012-10-01T05:05:37.087 に答える
3

貪欲なアルゴリズム(現在行っていること) は、通常、この種のことに対して選択され、自動販売機で使用される最終状態マシンとして実装されます (この特定のケースの場合)。

貪欲なアルゴリズムは、変更中に与えるコインの最小数を決定します。これらは、貪欲なアルゴリズムをエミュレートするために人間が実行する手順です

于 2012-10-01T05:01:37.903 に答える
0

最大の額面を使い果たすという仮定は、毎回最良の解決策ではありません。例：

Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents 

Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents (min)
As per logic of exhausting largest coins first, we would end up with one
coin of 9 cents and 2 coins of 1 cent

詳細については、この回答を参照してください。

于 2016-05-09T12:33:15.047 に答える