1

私は持っているお金の全額を渡されました。これで、各桁 (1 から 9) を書き留めるのにかかるコストがわかります。では、そこから最大数を作成するにはどうすればよいでしょうか。この問題に対する動的計画法のアプローチはありますか?

例：

利用可能な合計金額 =
各桁 (1 から 9) の 2 コスト =9, 11, 1, 12, 5, 8, 9, 10, 6
出力:33

4

3 に答える 3

2

動的プログラミングは必要ないと思います。次のことを行ってください。

  • できるだけコストがかからない数字を選びます。
  • これで数字ができました (1 種類の数字のみで構成されています)。
  • 最初の桁を、余裕のある最大の桁に置き換えます
  • お金が残っている場合は、お金がなくなるまで 2 回目、3 回目と同じように繰り返します。

これが機能する理由:

11111>9999と91111> 88888、つまり、次のようにするのが最善であると考えてください。

  • できるだけ多くの桁を選択します。これは、最も安い桁を選択することによって行われます。
  • 次に、これらの数字を左から、余裕のある最大値の数字に置き換えます (これは、最初にいくつかのより高価な数字を選ぶよりも常に優れています)。

最適化：

これを効率的に行うには、より大きな数字よりもコストがかかる数字を破棄します: (より大きな値を持つ安価な数字の代わりにその数字を選択することは決して良い考えではないため)

Given:
9, 11, 1, 12, 5, 8, 9, 10, 6
Removing all those where I put an X:
X, X, 1, X, 5, X, X, X, 6
So:
1, 5, 6

これで、バイナリ検索を実行できます (値がどの桁から来たかを覚えておいてください) (ただし、9 桁のみの場合、バイナリ検索は、すでにマイナーな実行時間に対して実際には驚くべきことではありません)。

実行時間：

O(n)(9 は定数であるため、最適化の有無にかかわらず)

于 2013-09-27T16:47:54.130 に答える
0

ナップザックの問題を解決する

と

  • コスト = 桁コスト
  • 値 = 桁数 (9 は 1 より優れています)

次に、降順で並べ替えます。

于 2013-09-27T16:46:39.163 に答える