問題タブ [coin-change]

目標額とコインの種類のリストが与えられた場合、私のコードは、目標額に到達するために必要な最小のコインを見つけることになっています。

例:

• C(78, [1, 5, 10, 25, 50]) = 6

  • 253x + 3xから 78 を作ることができる1ので、6 コインが必要です。

• C(48, [1, 7, 24, 42]) = 2

  • 48 = 2x24なので、2 コインで十分です。

• C(35, [1, 3, 16, 30, 50]) = 3

  • 162x + 1xから 35 を作ることができる3ので、コイン 3 枚で十分です。

for ループでコードを作成しましたが、再帰的にするにはどうすればよいですか?

コイン問題の動的計画法の手法で行列がどのように見えるべきかについて、私は混乱しています。1c、5c、10c、および 25c の金種があり、make-change(10) を呼び出すとします。つまり、10 セントを変更したいのですが、最終的な行列/配列はどのように見えるでしょうか。プログラムの最初に配列を割り当てたいので、これを知る必要があります。ここでコードを探しているわけではありません。

重複の可能性：
再帰的に変更を加える：すべての組み合わせを印刷するようにアルゴリズムを変更するにはどうすればよいですか？

コインパターンカウント問題（値Nとコインの固定セットが与えられた場合、合計でNになるコインの組み合わせの数を計算する必要があります）で、組み合わせをカウントするのではなく組み合わせを印刷する場合は、アプローチ ？そのために動的計画法を使用する必要がありますか？

I understand how the greedy algorithm for the coin change problem (pay a specific amount with the minimal possible number of coins) works - it always selects the coin with the largest denomination not exceeding the remaining sum - and that it always finds the correct solution for specific coin sets.

But for some coin sets, there are sums for which the greedy algorithm fails. For example, for the set {1, 15, 25} and the sum 30, the greedy algorithm first chooses 25, leaving a remainder of 5, and then five 1s for a total of six coins. But the solution with the minimal number of coins is to choose 15 twice.

What conditions must a set of coins fulfil so that the greedy algorithm finds the minimal solution for all sums?

したがって、典型的な硬貨の両替問題では、額面 x1、x2、...、xn の無制限の硬貨を使用して値 v を両替できるかどうかを判断する必要があります。各コインを最大1回使用しても同じ問題がありますか?

元の問題については、値のプレフィックスを繰り返し処理して、v-x_i を変更できるかどうかを確認できることはわかっていますが、金種ごとに最大で 1 つのコインに制限されている場合、途方に暮れています。

始めるためのヒントはありますか？宗派の接頭辞を繰り返し処理できると思っていたのかもしれません。確かではありませんが...

コインの変更問題の解決策を理解しようとしていますが、いくつかの問題があります。

Algorithmistには、以下に示す動的プログラミング ソリューションの疑似コード ソリューションがあります。

O(n^2)これは、2 次元配列を使用して同じ答えを何度も再計算することを避ける標準的なアルゴリズムです。

私の問題は 2 つあります。

1. 基本ケースを定義し、table[][]初期値として組み込む方法
2. テーブルからさまざまなシーケンスを抽出する方法

問題 1 に関しては、このアルゴリズムには 3 つの基本ケースがあります。

• if n==0, return 1
• if n < 0, return 0
• if n >= 1 && m <= 0, return 0

それらを に組み込む方法がtable[][]わかりません。最後に、配列からソリューション セットを抽出する方法がわかりません。

私はコイン1、2、4、10、20、40、100、200、400、1000、2000セントのセットを持っています。特定の金額（<= 6000）を支払う方法がいくつあるか知りたいです。C ++での私の現在の解決策は、動的計画法を使用することです。

しかし、私の出力は正しくありません：-956301262。オーバーフローの問題が原因ですか？

そこで私は、特定の金額に到達できる特定の金種セットの「コイン」の最小数を計算する問題に対して、再帰的なアルゴリズムを作成しました。アルゴリズムは機能しているように見えますが、再帰的であり、いずれかを選択する前に可能なすべてのオプションを計算するため、使用されている金種も印刷する方法を考え出すのに苦労しています. したがって、基本的に、使用可能なコインの最小数を計算できますが、どのコインであるかは計算できません。これが、コードと、それを駆動するために使用している小さなメイン メソッドです。アルゴリズム自体を合理化するための提案も大歓迎です。

使用できるコインの最小数を計算するような方法で、コイン変更の問題を解決しようとしました。http://www.algorithmist.comのアルゴリズムの投稿を使用しました。アルゴリズムは次のとおりです。

しかし、コードを書くと無限に実行されます。

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

何が間違っている可能性がありますか？