90

I understand how the greedy algorithm for the coin change problem (pay a specific amount with the minimal possible number of coins) works - it always selects the coin with the largest denomination not exceeding the remaining sum - and that it always finds the correct solution for specific coin sets.

But for some coin sets, there are sums for which the greedy algorithm fails. For example, for the set {1, 15, 25} and the sum 30, the greedy algorithm first chooses 25, leaving a remainder of 5, and then five 1s for a total of six coins. But the solution with the minimal number of coins is to choose 15 twice.

What conditions must a set of coins fulfil so that the greedy algorithm finds the minimal solution for all sums?

4

8 に答える 8

21

マトロイド ( https://en.wikipedia.org/wiki/Matroid )を形成するセットを使用して、貪欲なアプローチを使用してコインの変更問題を解決できます。簡単に言えば、マトロイドは、次の条件を満たす順序付けられたペア M = (S,l) です。

  1. S は有限の非空集合
  2. l は S の部分集合の空でない族であり、独立部分集合と呼ばれ、B->l かつ A が B の部分集合である場合、A -> l となる
  3. A-> l、B-> l および |A| の場合 < |B| の場合、AU {x} ->l となる要素 x-> BA が存在する

コイン交換の問題では、S はすべてのコインの値を降順で並べたものです。S のコインの最小数によって V の値を達成する必要があります。

この場合、l はすべてのサブセットを含む独立したセットであり、各サブセットについて以下が成り立ちます: それらの値の合計は <=V

集合がマトロイドの場合、答えは l の最大集合 A であり、これ以上 x を追加することはできません

確認するために、集合 S = {25,15,1} でマトロイドのプロパティが成り立つかどうかを確認します。ここで、V = 30 ここで、l には 2 つの部分集合があります: A = {25} と B= {15,15} |あ| < |B| の場合、AU {x} ->l となる要素 x-> BA が存在する (3 によると) したがって、{25,15} は l に属するはずですが、25+15>30 であるため矛盾しています。

したがって、S はマトロイドではないため、貪欲なアプローチは機能しません。

于 2013-09-16T10:22:06.010 に答える
-5

覚えやすいケースは、コインのセットが昇順でソートされていて、次のようになっている場合です。

coin[0] = 1
coin[i+1] >= 2 * coin[i], for all i = 0 .. N-1 in coin[N]

次に、そのようなコインを使用した貪欲なアルゴリズムが機能します。

照会している範囲によっては、(必要なコインの数に関して) より最適な割り当てがある場合があります。この例は、範囲 (6..8) を検討していて、コインが <1, 2, 4, 8> ではなく <6, 7, 8> である場合です。

N+ で完了するコインの最も効率的な割り当ては、上記の一連のルールと同じであり、コイン 1、2、4、8 ... が得られます。これは単に任意の数値の 2 進数表現です。ある意味で、基地間の会話はそれ自体が貪欲なアルゴリズムです。

>= 2N の不等式に関する証明は、このディスカッションで Max Rabkin によって提供されています 。

于 2012-11-26T08:47:35.323 に答える