1

与えられた金額の釣り銭を計算するコードは次のとおりです。ただし、釣り銭の金額に対して最小のコイン数を指定するように記述されていませんが、コードは必要な最小コイン数を指定しているようです。必要なコインの最小数を与えられない場合が必要です。

def change(amount):
    money = ()
    for coin in [25,10,5,1]:
        num = amount/coin
        money += (coin,) * num
        amount -= coin * num

    return money

print change(59)

output is: 
(25, 25, 5, 1, 1, 1, 1)
4

3 に答える 3

3

ウィキペディアが述べているように、その可能なコインのセットに対して、貪欲なアルゴリズムは常に最適な結果を返します。ただし、「[...] コインの額面が 1、3、および 4 の場合、6 を作るために、貪欲なアルゴリズムは 3 つのコイン (4,1,1) を選択しますが、最適なソリューションは 2 つのコイン (3,3) です。 " .

したがって、そのアルゴリズムで最適ではないソリューションに直面するには、可能なコインのセットを変更する必要があります。

于 2013-11-03T00:14:07.710 に答える
0

テスト ケースの望ましい結果をそのまま受け取ると、負の数を指定すると、必要な最小数のコインを取得できなくなる可能性があります。

print change(-1)
(10, 10, 1, 1, 1, 1)
于 2013-11-03T00:22:33.040 に答える