2

通常、コインの両替問題には次の再帰関係があります: (Pは両替が必要な合計金額でd_i、コインは利用可能です)

しかし、次のようにすることはできませんか: (Vは指定されたソートされた使用可能なコインのセットであり、 は指定さiれた最高値のコインのj添字です)Vj

C[p,Vi,j] = C[p,Vi,j-1]     if Vj > p
          = C[p-Vj,Vi,j] + 1  if Vj <=p

私が書いたものに何か問題がありますか？ソリューションは動的ではありませんが、より効率的ではありませんか?

4

2 に答える 2

4

を考慮してくださいP = 6, V = {4, 3, 1}。4, 1, 1代わりにを選ぶ3, 3ので3、最適な の代わりにコインを選び2ます。

于 2012-10-25T19:11:19.883 に答える
0

あなたが書いたものは、特定の条件下でのみ機能する貪欲なアルゴリズムに似ています。(参照 -最小限のコインの変更を見つけるのに貪欲なアルゴリズムで十分かどうかを確認する方法は? )。

また、あなたのバージョンではVi、繰り返し内で実際に使用していないため、メモリの無駄です

于 2012-10-25T19:09:31.063 に答える