問題タブ [coin-change]

マシンが引き継ぐと、すべてのコインの額面は 2 の累乗になります: 1 セント、2 セント、4 セント、8 セント、16 セントなど。コインの金額に制限はありません。値することができます。

硬貨の値の合計が n の場合、硬貨のセットは n に変化します。たとえば、次のセットは 7 を変更します。

1 セント硬貨 7 枚 1 セント硬貨 5 枚、2 セント硬貨 1 枚 1 セント硬貨 3 枚、2 セント硬貨 2 枚 1 セント硬貨 3 枚、4 セント硬貨 1 枚 1 セント硬貨 1 枚、2 セント硬貨 3 枚2セント硬貨1枚、4セント硬貨1枚 したがって、7に両替する方法は6通りあります。

正の整数 n を受け取り、これらの未来のコインを使用して n を変更する方法の数を返す関数 count_change を作成します。

ツリー再帰を使用しようとして、この質問に1時間取り組んできましたが、うまくいきません。現在の金額の 2 つのブランチ (1 と現在の金額) を使用することを考えていましたが、可能な限り最大のコイン値ですが、結果は決して満足できるものではありません。

アプローチ方法を教えてください... thx!

コインを交換するプログラムを書いています。iまたはjプログラムを印刷するためにループでprintfを記述すると、良い結果が得られますが、削除するとプログラムが停止します。メモリに問題があると思いますが、QT の Windows で書いていて、valgrind にアクセスできません。

誰でもこれを確認できますか？最初に金種の数を指定し、2 番目に金種を指定し、最後に金額を指定します。

例えば：

結果は 2 になるはずです。

結果は NO でなければなりません。

コインチェンジの問題を解決しようとしています：

数値 k のリストが与えられた場合、与えられた量 m に変更を加える方法はいくつありますか。

リソースの 1 つとして、次の疑似コードがあります。

しかし、私はこの疑似コードを理解していません。算術記号が後ろにあるはずのときに、前に算術記号があります。else文が始まるところまでは理解できました。しかし、else ループに入ると、何が起こっているのかわかりません。この疑似コードを、else 句の後の各ステップで実行するいくつかの論理的な処理に減らしていただけますか?

または、この問題を解決するために、この疑似コードよりも役立つ記事はありますか。これをグーグルで検索すると、最適な変更を求める問題しか見つかりませんが、それは必要ありません。

注これはコーセラ コースであり、直接の回答は倫理規定に違反するため、コードを教えないでください。

UPDATE @EmilVikströmが親切にそこで何が起こっているのかを親切に説明してくれたので、スキームと同じはずの小さな疑似コードを作成しようとしました(これはelse句にすぎません。残りはかなり自明です自分）。

これは策略の結果でしょうか。そうでない場合、どこで間違ったのですか？これはコーセラの倫理規定に違反するため、もう一度答えないでください（できれば正しい方向に向けてください）。

私が書いたコードは、動的計画法を使用して基本的なコインの変更の問題を解決し、変更を行うために必要なコインの最小数を示します。しかし、各コインプレイのカウントを最小数に保存したいと思います。

私がやろうとしているのは、配列count[]を初期化することであり、ハッシュのように、が見つかるcoin[j]たびに の数を増やします。しかし、これは、に対応するものを見つけるたびにコインを追加するため、私が望むようには機能していません。したがって、この数字は、最終回答のコインの最終カウントではありません。mincount[coin[j]]++mincoin[j]

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

Coin Change は、コイン (C[0]、C[1]...C[K-1]) を使用して N セントの合計を得る方法がいくつあるかを尋ねる非常に人気のある問題です。DP ソリューションは、メソッド s(N, K) = s(N, K-1) + s(NC[K-1], K) を使用することです。ここで、s(N,K) は到着する方法の量です。最初の K コイン (昇順でソート) の合計 N で。これは、最初の K コインを使用して N セントを稼ぐ方法の量は、K 番目のコインを使用せずに同じ金額に到達する方法の量の合計に、N-K 番目のコインに到達する方法の量を加えたものであることを意味します。どうすればこの解決策にたどり着くことができるのか、またそれが論理的にどのように理にかなっているのか、私には本当にわかりません。誰か説明してくれませんか？

値 N が与えられ、N セントを両替したい場合、S = { S1, S2, .. , Sm} 価値のコインのそれぞれが無限にある場合、両替する方法はいくつありますか? コインの順番は問いません。

以下のコードを書きましたが、常に実際の回答よりも 1 つ少ない数を返します。これがソリューションをコーディングする正しい方法であるかどうか知りたいですか?

コインの両替問題に対するボトムアップのアプローチを構築しています。要求された変更を提供するために必要な最小数のコインを提供する必要があります。指定された金種が値を形成できないため、変更を指定できなかった可能性があります。

たとえば、指定された金種が {4, 8} で、5 の変更を要求した場合、5 を発行することは不可能です。以下のプログラムを作成しましたが、要求された変更を形成することが不可能でない限り、ほとんどの状況でうまく機能します。 . たとえば、金種がちょうど {4} の場合に 5 をリクエストすると、偽の 1 つが返されます。この問題を解決するにはどうすればよいですか?

ここで、P は要求された変更を表し、S はインデックス 0 から S - 1 までの配列 denominations[] に格納されている金種の数です。dp は -1 に初期化された計算用の 2 次元配列です。

ご協力ありがとうございました。