6

私は、Project Euler でいくつかの問題/演習に取り組んでおり、Python を使用していくつかの最適なアルゴリズムとプログラミングのイディオムを練習/学習することを望んでいます。

合計が 100 になるように、少なくとも 2 つの値を使用してすべての一意の組み合わせを見つけるように要求する問題に遭遇しました。

貪欲なアルゴリズムについては聞いたことがありましたが、理解も使用もしていませんでした。やってみようと思いました。これが適切な方法であるかどうかはまだわかりません。

def greedy(amount):
    combos = {}
    ways = {}
    denominations = [1,5,10,25]
    ## work backwards? ##
    denominations.reverse()
    for i in denominations:
    ## check to see current denominations maximum use ##
        v = amount / i
        k = amount % i
    ## grab the remainder in a variable and use this in a while loop ##
        ways.update({i:v})
    ## update dictionarys ##
        combos.update({i:ways})
        while k != 0:
            for j in denominations:
                if j <= k:
                    n = k/j
                    k = k % j
                    ways.update({j:n})
                    combos.update({i:ways})
        ways = {}
    return combos

これがオイラーの問題を解決する方法ではないことはわかっていますが、このアルゴリズムを使用する最適な方法を理解し、学びたいと思っていました。私の質問は、これは適切な貪欲なアルゴリズムと見なされるでしょうか? そうでない場合、私は何を間違っていますか。正しい場合、最適化を改善できますか?

4

3 に答える 3

4

貪欲なコイン アルゴリズムは、所定の金額を変更するための最適な方法を計算します。それは私たちのコインの金種で動作しますが、コインのデノミネーションで失敗する可能性があります (例: 7 セント硬貨と 12 セント硬貨)

ここにそれの再帰的な実装があります

>>> def pickBest(coins,due):
...     if due == 0: return []
...     for c in coins:
...        if c<= due: return [c] + pickBest(coins,due-c)
...
>>> coins = [1,5,10,25]
>>> coins = sorted(coins,reverse=True)
>>> coins
[25, 10, 5, 1]
>>> print pickBest(coins,88)
[25, 25, 25, 10, 1, 1, 1]

ただし、あなたが述べたように、これが問題の解決に役立つとは思いません

あなたはおそらくそれを再帰的な問題と考えたいでしょう

100 = 99 + 1
100 = 98 + 2  (2 = 1 + 1)
100 = 98 + (1 + 1)
100 = 97 + 3 (3 = 1 + 2)
100 = 97 + 2+1 (recall 2 = 1+1)
100 = 97 + 1+1 + 1
...

少なくともそれは私が思うことです、私は間違っているかもしれません..（実際、私は間違っていると思います）

于 2012-07-27T21:18:52.773 に答える
2

質問を編集して、特定のコインのセットを使用して特定の金額を変更する最適な方法は何かを尋ねました。少なくとも、それがあなたが求めている質問だと思います。利用可能なコインの各金種の数に制限がないか、少なくとも各金種のコインを好きなだけ使用できると仮定します。

たとえば、1 セント、5 セント、10 セント、25 セントの硬貨を使って 1 ドルを両替する問題を考えてみましょう。1ドルは100セントです。貪欲なアルゴリズムは、常に最大のコインを取ります。したがって、最初のステップでは、最大のコインが目標額以下であるため、出力に 25 セントのコインを追加し、目標を 75 セントに減らします。2 番目のステップでは、最大のコインが減少した目標以下であるため、出力に 25 セントのコインを追加し、目標を 50 セントに減少させます。3 番目のステップでは、最大のコインが減少した目標以下であるため、出力に 25 セントのコインを追加し、目標を 25 セントに減少させます。4 番目のステップでは、最大のコインが減少した目標以下であるため、25 セントのコインを追加して、目標を 0 セントに減少させます。これで何もすることがなくなったので、出力は 25 セント硬貨 4 枚です。

あまり面白くなかったので、47 セントを目標にもう一度試してみましょう。最初のステップは 25 セントのコインを出力し、ターゲットを 22 セントに減らします。現在、25 セント コインを出力することはできなくなっているため、10 セント コインである削減目標以下の最大のコインを出力し、目標を 12 セントに削減します。3 番目のステップで、減少した目標以下の最大のコインは 10 セントなので、そのコインを出力し、目標を 2 セントに減少させます。次の 2 つのステップは、それぞれ 1 セント硬貨を出力し、ターゲットをゼロに減らします。したがって、出力は 25 セント コイン 1 枚、10 セント コイン 2 枚、1 セント コイン 2 枚の合計で 47 セントになります。

そこからコードを書くのはあなたに任せます。あなたが言ったように、それはオイラー 76 とは何の関係もありません。

最初のコメントに対応する UPDATE。現在は消えています。

あなたのコードを何と呼ぶべきかわかりません。貪欲という言葉で十分だと思います。途中の手順を確認できるように、デバッグ出力を含めて、これを行う方法を次に示します。

def greedy(amount, denoms):
    result = []
    while (amount > 0):
        print amount, denoms, result
        if (amount >= denoms[0]):
            num = amount // denoms[0]
            amount -= (num * denoms[0])
            result.append([denoms[0], num])
        denoms = denoms[1:]
    return result

print greedy(100, [25,10,5,1])
print ""
print greedy(100, [10,5,1])
print ""
print greedy(100, [5,1])
print ""
print greedy(100, [1])
print ""
print greedy(47, [25,10,5,1])

出力は次のとおりです。

100 [25, 10, 5, 1] []
[[25, 4]]

100 [10, 5, 1] []
[[10, 10]]

100 [5, 1] []
[[5, 20]]

100 [1] []
[[1, 100]]

47 [25, 10, 5, 1] []
22 [10, 5, 1] [[25, 1]]
2 [5, 1] [[25, 1], [10, 2]]
2 [1] [[25, 1], [10, 2]]
[[25, 1], [10, 2], [1, 2]]

それは役に立ちますか？

于 2012-07-28T00:00:39.297 に答える
1

Euler 76 では、数値の分割を計算するよう求められます。これはコインの問題ではなく、貪欲なアルゴリズムでもありません。数の分割を数える方法はオイラーによるもので (驚きです!)、ほとんどのアルゴリズムや数学のテキスト、または Google で調べることができます。プログラムはほぼ瞬時に実行されるはずです。

ちなみに、Project Euler での答えは、P(0)=1 という慣習を無視しているため、通常の P(100) の計算よりも 1 少なくなります。したがって、パーティションを計算する関数を作成すると、Euler 76 の答えは P(100)-1 になります。

私はブログでパーティションについて 2 回説明しました。1 回目はパーティションの数を計算したとき、もう 1 回はすべてのパーティションを列挙したときです。

于 2012-07-27T23:35:57.557 に答える