問題タブ [coin-change]

購入金額から変更金額 (クォーター、ダイム、ニッケル、およびペニー) を計算する最も効率的な方法を探しています。購入金額は 1 ドル未満で、おつりは 1 ドルからです。誰かがどれだけの 4 セント硬貨、10 セント硬貨、5 セント硬貨、1 セント硬貨を取り戻すかを知る必要があります。

辞書を設定した方がよいでしょうか。

数か月前に面接の準備のために書いていたコードを見つけました。

私が持っていたコメントによると、それはこの問題を解決しようとしていました:

セント単位のドル価値 (例: 200 = 2 ドル、1000 = 10 ドル) が与えられた場合、そのドル価値を構成するコインのすべての組み合わせを見つけます。ペニー (1¢)、ニッケル (5¢)、ダイム (10¢)、クォーター (25¢) のみが許可されています。

たとえば、100 が与えられた場合、答えは次のようになります。

これは、反復と再帰の両方の方法で解決できると思います。私の再帰的な解決策は非常にバグが多く、他の人がこの問題をどのように解決するのか疑問に思っていました。この問題の難しい部分は、可能な限り効率的にすることでした。

そう; 私は SICP を使って作業しようとしている愛好家です (無料です! )。最初の章には、アメリカの硬貨で両替する方法を数えるための手順の例があります。(change-maker 100) => 292. 次のように実装されています。

ともかく; これはツリー再帰手順であり、作成者は同じ問題 (つまり、固定スペース) を解決するための反復手順を見つけることを「課題として残します」。私はこれを理解したり、イライラした後に答えを見つけたりすることができませんでした。それは私の側の脳のおならなのか、それとも作者が私をからかっているのか疑問に思っています.

各金種の硬貨の数が無限である硬貨交換問題のアルゴリズムのアイデアを知りたいです。DPを適用する方法を意味します（標準のコイン交換問題のように）たとえば、セット1、10、15の場合、35の変更で--10の2コインと15の1コイン

また、このためのブルートフォーシングアルゴリズムのアイデアを教えてください。私はすべてのセットを繰り返すことを知っています。しかし、ブルートフォース中に各コインの数を変える方法

私は最近、Objective-C (またはプログラミング) の勉強を始めたばかりで、単純なプログラムで行き詰っています。

私は 4 分の 1、10 セント硬貨、5 セント硬貨、および 1 セント硬貨でおつりを作ろうとしていますが、思いついた解決策では、5 セント硬貨または 1 セント硬貨にランダムな値が与えられることに気付きました。

元。25 の変更は、「変更は 1 四半期、0 ダイム、-1881139893 ニッケル、および 4096 ペニスです」となります。

例2。30 の変更は、「変更は 1 四半期、0 ダイム、1 ニッケル、および 4096 ペニスです」となります。

この動作を修正するには、何を追加/変更できますか?

また、4 つの異なる if ステートメントを実行するよりも優れた解決策はありますか?

ありがとう！

以下は私のコードです：

こんにちは私は私が変更を取り戻すことができる方法がいくつあるかを見つけるアルゴリズムを作成しようとしています。しかし、私は実装を正しく行うことができません。私は4を取得し続けますが、6を取得する必要があり、その理由がわかりません。

これはC＃での私の実装であり、 http：//www.algorithmist.com/index.php/Coin_Changeの擬似コードから作成されます。

この問題で使用される可能性のあるサブセット合計を生成するプログラムを作成しました。

$1 コインが 3 枚、$2 コインが 2 枚、$5 コインが 3 枚、$10 コインが 1 枚あるとします。これらのコインから $10 を得る方法は 4 つあります。$X1 コインが n1 枚、$X2 コインが n2 枚.... nm $Xm 枚ある場合、これらの限られた数のコインから $X を取得するには、何通りの方法がありますか?

{ X1, X1..... X1, X2, X2.......... X2, ..., ..., ........... .., Xm, Xm... Xm} を実行し、サブセットの合計を実行すると、確かに $X の結果が得られます。しかし、セット {n1, n2, n3.... nm} 、 {X1, X2, X3.... Xm} を使用する方法が見つかりませんでした。ナップザック問題の一種だと友達に言われましたが、どうしてかはわかりません。

これは私が書いたものの部分的なコードです:

もう少し丁寧に説明していただけると助かります。

編集:この質問は、コンピューター サイエンスの stackexchange に適していますが、私の古い質問なので、ここで編集しています。

この問題は、包含除外の原則で解決できます。コインの値は固定されているが、各コインの数はクエリごとに異なる場合に便利です。

way [v]が$x1、$x2、.. $xmで$vを作成する方法であり、それぞれが必要な回数だけ使用されるとします。ここで、 $x1 の n1 個のみを使用している場合、少なくとも( n1 + 1) 個の $x1 (実際には [ v - (n1 + 1)x1 ] の方法) を使用して構成を減算する必要があります。さらに、$x2のn2個だけを使用している場合は、ウェイ[ v - (n2 + 1)x2 ] も減算する必要があります。

ここで、少なくとも ( n1 + 1) $x1および ( n2 + 1) $x2が使用される構成を 2 回減算したため、ウェイを追加する必要があります[ v -(n1 + 1)x1 - (n2 + 1) x2 ] など

特に、

N = すべてのコインができるだけ多く使用される構成のセット、

Ai = 1 <= i <= mの場合、少なくともni + 1 個の$xiが使用される構成のセット

求めている結果 = | ん| - | A1 | - | A2 | .. - | 午前| + | A1とA2 | + | A1とA3 | + ... - | A1とA2とA3 | .....

無制限のコインで構成の数を計算するコードは、実際にはより単純です。

こんにちは、みなさん。質問があります。私は Visual Basic Express で作業しており、トランザクションからの変更を計算することになっています。

では、どのコードを使用しますか? 部分的に機能していますが、少し混乱し始めています。

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

もっと情報が欲しかったあなたのために：

私が 1 ドル持っていて、何かを購入するために店に行ったとします。ユーザーに、費やした金額を入力してから、変更を計算して画面に出力するように依頼する必要があります。

次に、最小限の数のクォーター、ダイム ニッケル、およびペニーを使用して、それを画面に印刷することになっています。

どんな助けでも大歓迎です。

合計が入力である ls のコインを返す「make-change」を作成しようとしていますが、可能な限り少ない数のコインを含める必要があります。例: (make-change 99)

=> (クォーター クォーター クォーター ダイム ダイム ペニー ペニー ペニー ペニー)

はい、私はこれに似た投稿があったことを知っていますが、それらをすべて調べた後、私はプログラミングに非常に慣れていないのでまだ立ち往生しており、与えられた答えはどれも私の問題に役立つほど具体的ではありませんでした。

質問。アイテムのコスト（1ドル以下）が与えられた場合に、購入者が50セント、20セント、10セント、5セント、および1セントのコインの数を与える効率的なACL（アルゴリズムコンピューター言語）アルゴリズムを記述します。彼らが1ドルを渡した場合に受け取ります。変更するコインの数を最小限に抑える必要があります。

質問は特定のプログラミング言語とは関係がなく、答えはif、if-else、whileループなどの単純なACL言語のみを使用でき、配列やその他の高度なコマンドは使用できません。

これが私がいる場所です：

ここにコードを入力アルゴリズム最小変更量

完成したコード、あなたの助けに感謝します！あいまいさが見られる場合、またはコードを簡略化するのに役立つ場合は、お知らせください。