問題タブ [coin-change]

nに与えられる可能性のあるすべての変更セットを列挙するために、Javaコインの変更問題を試しています。

私の論理は次のようになります。

私のコード:

これは、すべての列挙の 1 セットだけを出力します。

出力：

質問:

それらの1つが終了したら、次の金種に移動する方法を理解するのに苦労しています...金種配列の次のインデックスに移動することになっていることは知っています...しかし、それは次のコインを追加するだけです.. . 次の最大のコインを追加してから、再帰的に次のコインにドロップするようにするにはどうすればよいですか?

ありがとう！

*編集**

望ましい出力: リストのリスト... 27 セント:

LIST{ [1, 0, 0, 2], [0, 2, 1, 2], [0, 1, 3, 2]... etc}

ネットで見た質問: メロンを売る農家が n 個のメロンを持っています。各メロンの重さ (整数 (ポンド)) は異なります。顧客はカットされていないメロンを丁度 m ポンド注文しました。ここで、農家は次の問題を抱えています。顧客を満足させることができる場合は、適切なメロンをできるだけ効率的に見つけて満足させるか、そうでなければ、顧客の要求を満たすことができないことを顧客に伝える必要があります。

注：これは宿題ではありません。指導が必要です。

私の答え: これは、コインの変更の問題 (ナップザック) とサブセットの問題 (バックトラック) に似ているようです。コインの変更: 重みをセット w = {5, 8, 3 , 2,....} に入れることができます。その後、サブセットの問題についても同じことが言えます。

基本的に、どちらの方法でもこの問題を解決できますか?

私の SML マニュアルで、特定の変更に必要な特定の種類のコインの数を計算する次の関数を見たことがあります。たとえばchange [5,2] 16 =[5,5,2,2,2]、2 枚の 5 コインと 3 枚の 2 コインがあると、16 になります。

次のコードは、バックトラッキング アプローチです。

それは機能しますが、正確にはわかりません。バックトラッキングとは何かは知っていますが、この特定の機能を理解していません。

私がこれまでに理解したこと:amtが 0 の場合、変更が計算され、最終的なリストにコンスされるものがないことを意味します。

「-list」にコインがもうない場合は、coin1 ステップ戻る必要があります。

これは私が迷っているところです: 例外を発生させることは、私たちが戻るのにどのように役立ちますか?

change私が見たように、ハンドラーは関数を呼び出そうとしますが、 " coins" パラメーターはnil? したがって、無限ループに入りますか？なぜ「戻る」のですか？

最後の節は私には明らかです。coin-value が釣り銭の残りの金額よりも大きい場合、残りのコインを使用して釣り銭を構築します。残りの量よりも小さい場合は、結果リストにコンスします。

私は Python プログラミング コースを行っており、それを実現する方法について頭を悩ませようとしています。私はいくつかのコードを書き、ポップアップするエラーを修正しようとしていますが、混乱して何も解決しないので、皆さんに頼ります. 私がこれまでに書いてきたことを見て、アイデアや提案が浮かんだら幸いです。特に、$2 より上または下の値を取得する必要がある最後の部分をどのように実行するかを理解するのに苦労しています。

私はこの演習を行っています：

ちょうど 2 ドルを稼ぐのに必要なコインの枚数をユーザーに入力させるおつりカウント ゲームを作成します。ユーザーに 5 セント硬貨、10 セント硬貨、20 セント硬貨、50 セント硬貨、1 ドル硬貨、2 ドル硬貨を入力するよう求める Python プログラムを実装します。入力されたこれらのコインの合計値が 2 ドルに等しい場合、プログラムはユーザーがゲームに勝ったことを祝福する必要があります。それ以外の場合、プログラムは、合計が正確に 2 ドルではないことを通知し、値が 2 ドルを上回るか下回るかを示すメッセージを表示する必要があります。

更新: 最後の関数にいくつかの変更を加えましたが、完全に正常に機能しました。

可能な限り最小限の変更量を与える必要があります。ケースの数を入力します。各ケースには、コインの数 (1 は必ずしもそれらの一部であるとは限りません) と、テストしたい数の数が含まれていました。次に、さまざまなコインを入力します。テストする別の数。

私のプログラムが動かない理由がわかりません。 1 は必ずしも変更の一部ではないため、プログラムを少し調整する必要がありました。

編集：「機能しない」とは、実際には何もしないことを意味します。入力を受け取り、何もしません。無限ループに入ると思います。

どのコインが使用されたかを追跡する一般的なコイン変更問題の DP ソリューションをプログラムしようとしています。これまでのところ、必要な最小量のコインを提供するために機能していますが、どのコインが何回使用されたかを取得する方法がわかりません。コインが使用されている場合、値を含む別のテーブル (ブール値) を設定しようとしましたが、正しく機能していないようです。何か案は？

セットのフロベニウス数は、セットの数の gcd が 1 である場合に存在します。すべての要素の gcd が 1 であるような最大 10 個の要素を持つ正の整数のセットが与えられた場合、セットのフロベニウス数をどのように計算できますか? ?

元の問題へのリンクは次のとおりです: https://icpcarchive.ecs.baylor.edu/external/62/6298.pdf シルベスターの公式を使用して、2 つの要素のセットのフロベニウス数を見つけることができます。

例：

20$ が与えられた場合、20$ をコインと交換する WAYS を数えたい = { 5$,10$, 15$} コインの順序は関係ありません。

ここで解決

解決策は次のとおりです: 方法の総数 = コインを使用する + コインを使用しない : total_ways = count( S, m - 1, n ) + count( S, m, nS[m-1] )

木の形で：