問題タブ [coin-change]

特定の金種のコインが与えられた場合に、変更するコインの最大数を見つけたいというこの問題を解決しようとしていました。

例 たとえば、価値が 3 と 5 のコインが与えられ、15 に両替したい場合、解決策は {3,3,3,3,3} になります (指摘してくれた JoSSte に感謝します) 同様に、値が 3 と 5 のコインで、7 に両替したい場合は、「解決できません」と表示する必要があります

次のように、最小数のコインを見つけるためにこれを行うことができました

if(n<0) と呼ばれるチェックがあることに注意してください。合計にならない組み合わせは、そのサイズを最小値にできない非常に大きな数に設定することによってオプションから削除されます。

ただし、上記を変更してコインの最大数を見つけるにはどうすればよいですか

setと integer をlist表す個別の正の整数の配列があります。すべてのサブセットを繰り返し処理し、各サブセットの合計が に等しいかどうかをチェックする代わりに、要素の合計が に等しいすべてのサブセットをカウントする最速の方法は何ですか?LSLSS

再帰を使用して、特定の金額を作るためのコインの最小量を見つけようとしています。必要なコインの最小量をリストできるコードがありますが、ソリューションを考え出すために使用されたコインを出力する方法を見つけることができないようです。同様の例を検索して見つけましたが、これに適切に適用できないようです。

これが私がこれまでに持っているものです：

これまでに実行されたコードの例:

これを行う方法について誰かが私に洞察を与えることができれば、それは大歓迎です。

コインの変更に関する質問と回答がたくさんありますが、これを見つけることができず、コインの変更の問題でさえあるのだろうかと思っています.

基本的に、私はさまざまなコインをたくさん持っていて、それぞれのコインは無限にあります。

つまり、さまざまな宗派のスタックがあるとします。各スタックは無限です。(つまり、無限の 25c コイン、無限の 2c コインなど)。

ただし、コインの各スタックの上には、下のコインよりも大きい (または等しい) 値を持つ特別なコインがあります。上のコインを使わないと下のコインにアクセスできません。

私が解決しようとしているのは、特定の合計を作るために必要なコインの最小数です。

これは解決可能な動的計画法だと思いますが、この制限を従来のソリューションに追加する方法がわかりません。

使用したらリストから特別なコインを削除して通常のコインに置き換えるかどうか疑問に思っていましたが、それがアルゴリズムを壊すかどうかを判断することはできません.

古典的なコインの変更の問題は、ここでよく説明されています: http://www.algorithmist.com/index.php/Coin_Change

ここでは、組み合わせがいくつあるかを知るだけでなく、それらすべてを出力したいと考えています。私の実装では、そのリンクで同じ DP アルゴリズムを使用していますが、DP テーブルに組み合わせの数を記録する代わりに、DP[i][j] = countテーブルに組み合わせを保存します。したがって、この DP テーブルには 3D ベクトルを使用しています。

テーブルを検索するときに必要なのは最後の行の情報だけなので、常にテーブル全体を保存する必要はないことに気づき、実装を改善しようとしました。

ただし、改善された DP ソリューションはまだかなり遅いように見えるため、以下の実装に問題があるか、さらに最適化できるかどうか疑問に思っています。ありがとう！

コードを直接実行できます。

私はセントで無制限の 4 種類のコインを持っています: [1, 5, 25, 50]. 正確な 1 ドルの変更を行うために正確な 48 枚のコインを選ぶ方法は? (いずれかの有効な方法で)

これを再帰的に解決する方法は知っていますが、DP を使用して解決することは可能ですか? どのように？ありがとう！

私はそれを述べているコイン変更問題を実装しようとしています

硬貨両替問題は、N セントの両替をしたい場合、値 N が与えられ、S = {S1, S2, . . . , Sm} の価値のある硬貨の場合、変更できる方法はいくつありますか? コインの順番は問いません。貪欲な方法で N セントを変更するすべての可能な方法を特定します。たとえば、N = 4 で S = {1, 2, 3} の場合、{1, 1, 1, 1}、{1, 1, 2}、{2, 2}、{1, 3}。したがって、出力は 4 になるはずです。N = 10 で S = {2, 5, 3, 6} の場合、{2, 2, 2, 2, 2}、{2, 2, 3, 3}、 {2, 2, 6}、{2, 3, 5}、{5, 5}。したがって、出力は 5 になるはずです。

注: これは、最適なソリューション (つまり、コインの最小数) を見つけなければならない元のコイン変更問題ではありません。

以下の Python 実装では、$check$ という名前のリストを使用しています。問題は、プログラムが実行時に同じ $check$ リストを使用しているため、間違った結果が得られることです。関数呼び出しに対してローカルな $check$ リストを使用する必要があります。誰かがこれから抜け出す方法を見つけることができますか..