7

ひねりを加えた古典的な動的プログラミングのコイン変更問題を解決しようとしています。これは宿題の質問です。私は完全な解決策を探しているわけではありません。私が間違っていることを確認するためのいくつかの指針を探しているだけです。

入力：

  • xある価値に対してコインで支払いたい金額。
  • d利用可能な金種のコインの数を表すセット(1c、5c、10c、25c、100c、200c)

出力：

  • 支払いのために手を交換する必要があるコインの最小数。

仮定:

  • キャッシュ レジスターのオペレーターは、無制限にコインを供給でき、最適な釣り銭の出し方を知っています。

私がこれまでにやろうとしたこと：

すべての要素 C[i] が、金額 i で交換されるコインの/最小/数になるように、配列 C を構築しようとしています。

C[0] = 0

C[i] については、使用可能なすべての硬貨の金種について、すべての C[i-di] の最小値に 1 を加えた値をとって計算します。次に、使用可能なコインから選んだコインを取り除きます。

このアプローチは単純なケースではうまくいくようですが、たとえば、次のような場合です。

99 99 0 0 0 1 0

正確に 99 セントをセント単位で支払う (99 コインの交換) よりも、2 コインの交換になる $1 の方が「安い」ため、私のアプローチは失敗します。

任意のポインタをいただければ幸いです。

4

2 に答える 2

1

問題は、探している値に到達したときに停止することのようです。値を x よりも大きくするためのコインの最小数を計算し続け、それにレジスタ オペレータが適切な変更を行うための最小コイン数を追加し、このより大きなリストから最小値を取得する場合は、次のことができるはずです。これに答えるために。

編集: 2 つの配列を使用した場合、これを少し単純化できます。1 つは作成できる値用で、もう 1 つはレジスタが作成できる値用です。そして、それらを何らかの方法で比較して、答えを得ることができます。

于 2012-07-03T23:02:16.903 に答える
0

重要なポイント: コインを繰り返すことができます。

解決策: ARR[i] = 値 i を作成するためのコインの最小数である配列を作成します。

擬似コード:

ARR[MAX] = {MAXIMUM VALUE} // set all elements in the array to have some big value
ARR[0] = 0

for C in coins
 for i = 0; i <= needed_value; ++i
   if i+C <= needed_value && ARR[i+C] > ARR[i]+1
     ARR[i+C] = ARR[i]+1

Example:
coins = {1, 3}
needed_value = 8
ARR[] = 0 INF INF INF INF INF INF INF INF
after using the coin with value 3, we will have
ARR[] = 0 INF INF 1 INF INF 2 INF INF
after using the coin with value 1, we will have
ARR[] = 0 1 2 1 2 3 2 3 4
=> we need 4 coins to make the sum
于 2015-02-01T01:54:16.660 に答える