Simple dynamic programmingEdit
古典的な動的計画法は、現在の閾値に合計するすべての小さい値の組み合わせを見つけることによって上向きに動作します。 このため、この動的計画法では、コインの種類をnとすると、O(nW)のステップ数を必要とする。
ImplementationEdit
以下は動的計画法の実装（Python3使用）であり、行列を使って部分問題の最適解を記録し、コインの最小枚数、または与えられたコインでお釣りを作る方法がない場合は「無限大」を返す。 5548>
def _get_change_making_matrix(set_of_coins, r: int): m = for _ in range(len(set_of_coins) + 1)] for i in range(1, r + 1): m = float('inf') # By default there is no way of making change return mdef change_making(coins, n: int): """This function assumes that all coins are available infinitely. n is the number to obtain with the fewest coins. coins is a list or tuple with the available denominations. """ m = _get_change_making_matrix(coins, n) for c in range(1, len(coins) + 1): for r in range(1, n + 1): # Just use the coin coins. if coins == r: m = 1 # coins cannot be included. # Use the previous solution for making r, # excluding coins. elif coins > r: m = m # coins can be used. # Decide which one of the following solutions is the best: # 1. Using the previous solution for making r (without using coins). # 2. Using the previous solution for making r - coins (without # using coins) plus this 1 extra coin. else: m = min(m, 1 + m]) return m
確率的畳み込み木による動的計画法編集
確率的畳み込み木は、より効率の良い動的計画法として使用することもできる。 確率的畳み込み木は、コインのペアをマージして、そのコインのペアによって生成できるすべての量（どちらのコインも存在しない場合、第1のコインだけが存在する場合、第2のコインだけが存在する場合、両方のコインが存在する場合）を生成し、その後、これらのマージした結果のペアを同じようにマージしていくものである。 このプロセスは、最終的に2つの結果のコレクションが1つにマージされるまで繰り返され、このようなマージ操作をW log(W)回行うバランスのとれた二分木を導く。 さらに、コインの値を離散化することにより、これらのマージ操作のそれぞれをコンボリューションによって実行することができ、これはしばしば高速フーリエ変換（FFT）を用いてより効率的に実行することが可能である。 このように、確率的畳み込み木を用いると、サブクアドラティックな数のステップで解を得ることができる。各畳み込みはn log(n)で実行でき、初期の（より多数の）マージ演算はより小さなnを用い、後の（より少ない）演算はWのオーダーのnを必要とする。
確率的畳み込み木ベースの動的計画法は、目標量Wの不確実性やファジー性によってそれが固定量ではなく離散分布となり、各コインの価値も同様にファジーであることが許され（例えば、為替レートを考慮する場合）、異なるコインが特定の頻度で使用される可能性のある、変化生成問題の確率的一般化も効率的に解くことができる。
Greedy methodEdit
米国や他の多くの国で使われているような、いわゆる正規のコインシステムについては、作られるべき残りの量より大きくない最大の額面のコインを選ぶ貪欲なアルゴリズムが最適結果を生む。 しかし、これは任意のコインシステムには当てはまらない。 例えば、コインの額面が1、3、4であった場合、6を作るには、貪欲なアルゴリズムでは3枚のコイン（4、1、1）を選ぶことになるが、最適解は2枚のコイン（3、3）である。 コインシステムが正準であるかどうか（つまり、貪欲アルゴリズムが常にその釣銭問題を最適に解くかどうか）を多項式時間でテストすることが可能である
。