問題タブ [coin-change]

最近、C++ で新しいプロジェクトに取り組む任務を与えられました...そして、それにどのようにアプローチするかについて、昼夜を問わず考えていました....残念ながら、その考えはうまくいかず、現在設計段階で奮闘中。基本的に前提は次のとおりです。

「有名な地元のデパートである Ruddles の経営陣は、店舗全体の顧客レジに特定の変更を実装することを決定しました。購入した顧客に正しい釣り銭を提供する際にスタッフに問題があるため、将来、釣り銭はから自動的に計算されます。商品の価格と顧客が入札した金額. 硬貨はレジによって自動的に払い出されます, 機械式払い出しが可能な機械に置き換えられようとしています.」

これはビジネス自体に関するほんの一部の情報です。以下は、私に与えられた要件仕様です。

特定の金種のコインの数が特定の値を下回ったときに警告を発します。したがって、そのようなプロビジョニングを提供する機能をソリューションに含める必要があります。現時点では、ハードウェアでメモを発行することはできませんが、将来の開発によって可能になる可能性があります。これらの改善が行われた場合、ソリューションはこれに対処できるようにする必要があります。したがって、そのようなハードウェアのアップグレードが行われた場合に、ソフトウェアにどのような変更が必要になるかを示す必要があります。」

現時点では、プロジェクトの次の要件にどのようにアプローチするかについて本当に確信が持てないので、私よりもはるかに知識が豊富で経験豊富な方がアドバイスや提案を提供できるかどうか疑問に思っています。時間と注意を払っていただければ幸いです。 :-)

これには複数の方法がある可能性があることは承知していますが、これまでのところ、完全にはわかりませんが、配列と永続化構造を使用する必要があることを理解しています..

幸いなことに、仕事をしている限り、過度に完成させる必要はありません。繰り返しになりますが、アドバイスやヒントをいただければ幸いです。ありがとうございました。

合計額1.15 Rs.(1 Rs. = 100 パイズ) が与えられると、合計 115 パイズとなり、パイズ8 coinsとして金種のリストが与えられ{1, 2, 5, 10, 20, 25, 50, 100}ます。6 coins1.15 Rs になる合計を見つけます。制約は、制限されたセットで与えられた金額について、私のソリューションから変更を与えることができないということです。ここでの限定セットは{5, 10, 20, 25}.

解決策や指針を高く評価します。

前もってお詫び申し上げます。この質問は、私が望む/必要な結果をもたらさない回答で以前に尋ねられたことを認識しています. Python3で次のことを行う関数を作成しようとしています:

指定された金額を生成するすべての方法 (コインの組み合わせ) を返す再帰関数が必要です。この関数には、金額とコインの 2 つの引数のみを含めることができます。再帰について頭を悩ますのに苦労したので、説明も大歓迎です。ありがとう。

これが私が現在持っているものです：

私は完全に立ち往生しており、これを解決する方法がわかりません。私が配列を持っているとしましょう

と数字

nに等しいarr内からの最短シーケンスが必要です。たとえば、 arr 内の次のシーケンスは n に等しい

したがって、上記の場合、答えは c2 です。なぜなら、それは arr で sum に等しい最短のシーケンスだからです。

上記の解決策を見つける最も簡単な方法は何ですか？どんなアイデアや助けも本当に感謝しています。

ありがとう！

編集:

• 配列を修正しました
• 配列は、正の値のみを持つ可能性があります。
• おそらく私自身の無知のために、サブセットの問題がこれをどのように修正するかわかりません。サブセットアルゴリズムは常に合計に等しい最短のシーケンスを提供しますか? たとえば、サブセットの問題は、上記のシナリオの答えとして c2 を識別しますか?

私は入力として持っています：

1. テストケースの数
2. 金額

出力として必要なもの：

1. 私たちが持っているさまざまなコインの数と各コインの価値。

プログラムは解決策があるかどうかを判断する必要があるため、出力は「はい」または「いいえ」のいずれかである必要があります。

動的計画法を使用してプログラムを作成しましたが、一度に1つのテストケースを入力した場合にのみ機能します。たとえば、一度に200のテストケースを作成すると、出力が常に正しくなるとは限りません。

テストケース間で状態が正しく保存されないという問題があると思います。私の質問は、どうすればこの問題を解決できるでしょうか？私はいくつかのアドバイスを求めているだけです。

これが私のコードです：

こんにちは私は学校の課題の変更計算機を作成しているときに問題が発生しています。それは本質的に、特定の金額に必要な最小の変更額を計算することです。

• 元。5.36ドル：
• 2ドル（2 $）
• 1ルーニー（1 $）
• 1四半期
• 1ダイム
• 0ニッケル
• 1ペニー

値と合計を一緒に計算できるように、すべての変数をdoubleであると述べました。整数（5.00、6.00、7.00）では問題なく動作するようですが、小数点以下を追加すると混乱します。私が5.25ドルと言うときのように、2ドル硬貨1ルーニーと1クォーターと言うべきです。丸め誤差か、計算に問題がある可能性があると思います。どんな助けでも大歓迎です。コードの計算は次のとおりです。

私は基本的に再帰によってコインの変更の問題を解決しようとしていますが、これが私がこれまでに持っているものです-:

s(i,sum) である最初の関数は私が作成したもので、c(sum,i) である 2 番目の関数はここから取得したものです - (www.algorithmist.com/index.php/Coin_Change)。

問題は、 count が常に予想よりもはるかに高い値を返すことです。ただし、アルゴリズムのソリューションは正しい答えを返しますが、この基本ケースを理解できません

インデックス (i) が 0 以下で、合計がまだ 0 でない場合、関数は 1 ではなく 0 を返すべきではありませんか?

また、 Project Eulerで正しい答えが得られたため、アルゴリズムのソリューションが正しいことも知っています。

50ドルという金額が与えられます。$1、$2、$5 などのいくつかの金種と、これらの金種の数、たとえば 1、5、6 が与えられます。これは、1 コイン/$1、5 コイン/$2 の紙幣、および 6 コイン/$5 の紙幣を意味します。これらのコインを使用して、この金額 $50 を形成する方法をいくつ見つけなければなりません。これを可能な限り最速で解決するための効率的なアルゴリズムを考えようとしています。金額が $60 を超えることはありませんのでご注意ください。

誰かがこの問題を解決するために使用できるアルゴリズムを提案できますか? これまで、この問題に対する再帰的な解決策を書きましたが、私の目的には遅すぎます。すぐにここに投稿します。

サンプル入力: 20 10 2 5 2

サンプル出力: 2

説明: 20 の量は 2 つの方法で作ることができます: 10*2 10*1 + 5*2

特定のコインで特定の金額を作成できる方法の数を調べたい.サンプル入力では、20 は作成する金額であり、次の行はコインの値とその値のコインの数、つまり 2 コインの値を示しています。 10.出力には、これらのコインで 20 を作成できる方法がいくつかあります。再帰的なソリューションを試しましたが、正しく機能しません。この問題を解決するには、どのアルゴリズムを使用すればよいですか?

なんらかの理由で常に答えが0になっています。すべての助けをいただければ幸いです。

この問題では、特定のコストでコインの交換回数を数える必要があります。

たとえば、コインの価値がである場合50, 20, 10, 5, 1、次のコストを形成できます。

5 =>（5）、（11111）、これは2つの方法です。

10 =>（10）、（5、5）、（5、11111）、（11111、11111）、これらは4つの方法です。

これが私の機能です。10のコストから物乞いする間違った結果を返しています（実際のウェイ数はわずか4であるのに対し、9ウェイを返します）

この関数を修正して、正しい数の方法を提供するにはどうすればよいですか？このアルゴリズムは正しいですか？ここで完全なコードとその出力を参照してください

注：私の問題はdp配列の初期化ではありません。を呼び出す前に毎回memset初期化するために使用しています。-1rec