0

私の問題は次のとおりです-

以下のようないくつかの数字があります-

  2
  2
  2
  2
  3
  3
 17
 17
 17
 17
 17
 17
 17
 17
 17
 34
 34
 34
 34
 34
 68
 68
 68
136

したがって、次の数値を入力として指定すると、出力は次のようになります-

[出力は、与えられた数値の合計であり、入力よりも大きい]

 Input  Output
     3      2,2
     4      2,2
     254    17,34,68,136
     7      2,3,3 [or also with 2,2,2,2 but if return same sum,
                   then number count should min]
     205    2,68,136
     10     2,2,3,3

結果を得るために、すべての組み合わせ（つまり、ブルートフォース）を試したいだけではありません。上記の状況で可能な効率的なアルゴリズムはありますか？

ありがとう。

4

1 に答える 1

0

ウィキペディアで可能な出発点を見つけました：

より一般的な問題では、指定された値 (必ずしも 0 ではない) になるサブセットの合計が求められます。上記のアルゴリズムを簡単に変更することで解決できます。各 xi が正であり、同じ定数によって境界付けられている場合、Pisinger は線形時間アルゴリズムを見つけました[3]。

あなたの基本的な問題は、その拡張版のように見えます。セットのサブセットを見つける必要がありますinput- またはそれに失敗する、合計するinput+1、または失敗する、合計するinput+2など。

では、結果が得られるまで、ターゲットの合計を増やしながら、Pisinger のアルゴリズムを繰り返し実行しますか? (私はその論文を読んでいないので、最小のサブセットを選択するタイブレーカー条件が Pisinger のアルゴリズムによって満たされるかどうかはわかりません。)

于 2011-05-04T18:49:08.710 に答える