11

部分和の問題に関連する問題があり、その違いによって問題が解決しやすくなるかどうか、つまり妥当な時間で解決できるかどうか疑問に思っています。

値 V、集合サイズ L、数列 [1,N] S が与えられたとき、S のサイズ L のサブセットの合計が V 未満になるのはいくつですか?

これは、次の 3 つの点でサブセット和問題とは異なります。

  1. 等しいサブセットの数ではなく、与えられた値よりも小さいサブセットの数を気にします。
  2. サブセットのサイズは固定されています。
  3. 存在するかどうかだけでなく、合計が V 未満になるセットの数を気にします。

これを解決する合理的に効率的なアルゴリズムはありますか?

編集: 明らかに、これは組み合わせ生成アルゴリズムを使用して O(N choose L) で実行できます。私が本当に興味を持っているのは、それを大幅に高速化する巧妙なハックです。

4

8 に答える 8

21

（の決定版）あなたの問題はまだNP完全です。問題を解決できれば、(各サブセット サイズについて) 合計が V 未満になるセットの数と、合計が V-1 未満になるセットの数を求めることができ、これら 2 つの数値の差は次のようになります。部分集合の合計が正確に V になるかどうかを教えてください。したがって、部分集合和の問題を解くことができます。[これは完全な証明ではありません。チューリング簡約であり、多数の簡約ではありません。]

ただし、時間 O(nLV) で実行される単純な動的計画法のソリューションがあります。[これが P=NP であることを証明しない理由は、V が入力サイズで指数関数的である可能性があるためです: n ビットでは、2 nまでの値を表すことができます。しかし、V が指数関数的でないと仮定すると、これは問題ではありません。]

num[v][k][i] は、合計が v になる S の最初の i 要素のサイズ k サブセットの数を示します。それらは (i ごとに) 次のように計算できます。

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

ここで、S[i] はシーケンスの i 番目の要素です。(合計が v になるサイズ k のセットは、S[i] を使用しないため、num[v][k][i-1] でカウントされるか、S[i] を使用します。つまり、残りのサブセットは k-1 個の要素を持ち、シーケンスの最初の i-1 個の数のみを使用し、合計すると vS[i] になります。) 最後に、V より小さい各 v について num[v][L][|S|] を数えます。 ; それがあなたの答えです。

また、慎重に行う場合は、3 番目の添え字を省略できます (i ごとに下向きにループを実行するなど)。わかりやすくするためにのみ含めました。

于 2008-12-17T21:26:53.647 に答える
2

私は証明を提示する準備ができていませんが、それは動的計画法に適しているように思えます: サイズ 2 のサブセットのリストを表にまとめ、それらをサイズ 3 のコンピューター サブセットに使用するなど。見込み客の小さなコレクション。

于 2008-12-17T21:13:11.223 に答える
1

頭に浮かぶ最適化の 1 つは次のとおりです。シーケンスを注文します (そうでない場合)。先頭から最初の L-1 アイテムを選択し、可能な限り最大の値になるような最後のアイテムを選択します (シーケンスで次に大きな値を指定すると、合計が大きくなりすぎます)。シーケンスの残りを破棄します。これらのアイテムは有効なサブセットの一部になることは決してないためです。

その後はまたフルサーチかな。しかし、他の最適化も可能な場合があります。

于 2008-12-17T21:04:13.147 に答える
1

部分集合和の問題に対する動的計画法の解は、この答えを含むテーブルを生成します (つまり、V x N のブール テーブルで、V は要素の最大数、N は、制約; <=N 要素の合計が <=V になる場合、各ブール値は true になります)。したがって、N * V が大きすぎなければ、許容できる高速アルゴリズムが存在します。サブセット合計ソリューションは、要素数が <= N/2 である、このテーブルの最高のセット要素です。

于 2009-11-16T22:32:19.570 に答える
1

正の整数のみの場合は、必要に応じて検証手順を実行できます。

セット内の L-1 個の最小の整数の合計を取ります。それが合計 X である場合、問題に解があると想定される場合、nX は最大要素よりも下でなければなりません。そういえば、これで他のLも消せますね……。

于 2012-04-13T15:47:33.583 に答える
0

1 つには、size=L を指定しているので、巧妙なことを考えられず、ブルート フォースを使用したとしても、最悪の場合 (N が L を選択) 個別の合計が得られるので、少しは良くなります。 n^^L より (L+1、各サブセットを合計するため)。

于 2008-12-17T21:04:35.017 に答える
0

これは、問題の n 選択 k カテゴリのように聞こえます。n の k-サブセットの生成については、Skiena の Algorithm Design Manual で説明されており、この本では、関連するサブセットを辞書順で (たとえば、再帰的に) 列挙することを提案しています。次に、各サブセットで合計と比較を行います。

ソートされたセットがある場合、おそらく解空間から不可能な解を取り除くことができます。

于 2008-12-17T21:04:35.453 に答える