algorithm - 可能な組み合わせの数を決定するアルゴリズム

Question

与えられた問題のアルゴリズムを書く必要があります: 無限のペニー、ニッケル、ダイム、クォーターがあります。合計が 99 セントになるようにコインのすべての組み合わせを出力するクラス メソッドを作成します。

順列nPrの問題のようです。そのためのアルゴリズムはありますか？

よろしく、プリヤンク

Answer 1

この問題はディオファントス方程式のようです。つまり、a * x + b * y + ... = nの場合、すべての文字が整数である解を見つけます。最も単純ですが、最も洗練された解決策は反復的な解決策ではありません（pythonで表示されます。変数lは数値1に似ているため、スキップすることに注意してください）。

dioph_combinations = list()
for i in range(0, 99, 25):
    for j in range(0, 99-i, 10):
        for k in range(0, 99-i-j, 5):
            for m in range(0, 99-i-j-k, 1): 
                if i + j + k + m == 99:
                    dioph_combinations.append( (i/25, j/10, k/5, m) )

結果のリストdioph_combinationsには、可能な組み合わせが含まれます。

Answer 2

最も簡単な方法は、おそらく少し時間をかけて問題について考えることです。比較的優れた再帰的なアルゴリズムがあり、メモ化または動的プログラミングソリューションへの作り直しに適しています。

Answer 3

この問題は古典的な動的計画法の問題です。ここでそれについて読むことができます

http://www.algorithmist.com/index.php/Coin_Change

Pythonコードは次のとおりです。

def count( n, m ):
    if n == 0:
        return 1
    if n < 0:
        return 0
    if m <= 0 and n >= 1:
        return 0

    return count( n, m - 1 ) + count( n - S[m], m )

ここで、S[m] は金種の値を示し、S は金種のソートされた配列です。