3

N 個の正の整数のコレクションがあり、それぞれが (比較的小さい) 定数 C で区切られています。値 K より大きい (または等しい) 最小の合計を持つこれらの数値のサブセットを見つけたいと考えています。

関連する数値はそれほど大きくありません (<100) が、最悪の場合でも優れたパフォーマンスが必要です。私は、Pisinger の動的プログラミング アルゴリズムをこのタスクに適用できるのではないかと考えました。それは O(NC) 時間で実行され、有界の正の数の要件をたまたま満たしています。

[編集]:番号はソートされておらず、重複している可能性があります。

ただし、これを自分で行うにはアルゴリズムを十分に理解していません。実際、それが基づいている仮定が今でも成り立つかどうかさえ定かではありません...

-このアルゴリズムを私のニーズに合わせることは可能ですか?

-または、同様に効率的な、使用できる別の線形アルゴリズムはありますか?

-誰でも疑似コードまたは詳細な説明を提供できますか?

ありがとう。

私が調査していた Subset-Sum コードへのリンク: Pisinger によるサブセット合計アルゴリズムへの高速ソリューション

（これが不適切な表現/フォーマット/その他である場合はお詫び申し上げます。私はまだStackOverflowに慣れていません...）

4

2 に答える 2

0

1つの解決策は次のとおりです。

T = {0}

for x in V
   for t in T
       T.insert(x+t)

for i in K to max(T)
   if (T.contains(i))
       return i

fail

これによりサブセットのサイズが得られますが、メンバーの出力に適応できます。

T の最大サイズは O(N) (C バウンドのため) であるため、実行時間は O(N^2) で、スペースは O(N) です。長さ NC のビット配列を T のバッキング ストアとして使用できます。

于 2013-06-18T03:39:45.690 に答える