3

Subset_sum_problemの解決に行き詰まっています。

整数のセット（S）が与えられた場合、合計が与えられたtarget（T）に等しい空でないサブセットを計算する必要があります。

例：与えられたセット、S {4、8、10、16、20、22}ターゲット、T=52。

制約：集合Sの要素数Nは8に制限されています。したがって、Nの上限が小さいため、NP時間解は許容されます。時間と空間の複雑さは実際には問題ではありません。

出力：

合計がT=52に正確に等しい可能なサブセットは次のとおりです。

{10、20、22}

{4、10、16、22}

Wikiや他のいくつかのページで提供されている解決策は、そのようなサブセットが存在するかどうかをチェックしようとします（YES / NO）。

上記の例で概説したように、考えられるすべてのサブセットを計算することは実際には役に立ちません。

このリンクでの動的計画法のアプローチは、そのようなサブセットを1つ提供しますが、そのようなサブセットはすべて必要です。

明らかなアプローチの1つは、力ずくの力を使用してすべての2 ^ Nの組み合わせを計算することですが、それが私の最後の手段になります。

私はいくつかのプログラム的な例（できればC ++）またはイラスト/例でそのようなサブセットを計算するアルゴリズムを探していますか？

4

4 に答える 4

2

N <= 8の場合、なぜ2 ^ nの解を使用しないのですか？非常に高速になるのは256の可能性だけです

于 2013-03-26T05:34:46.633 に答える
2

サブセット和問題の動的計画法テーブルを作成するときは、そのほとんどをそのように初期化します（質問で参照されているウィキペディアの記事から引用）。

    Q（i、s）：= Q（i − 1、s）または（xi == s）またはQ（i − 1、s − xi）

これにより、テーブル要素が0または1に設定されます。

この単純な式では、1を与える可能性のあるいくつかのケースを区別することはできません。

ただし、代わりに、次のように、これらのケースを区別できる値にテーブル要素を設定できます。

    Q（i、s）：= {Q（i − 1、s）！= 0} * 1 + {xi == s} * 2 + {Q（i − 1、s − xi）！= 0} * 4

次に、最後の要素からテーブルをトラバースできます。すべての要素で、要素の値は、要素からの可能なパスが0、1、または2つあるかどうか、およびそれらの方向を示します。すべてのパスは、合計でTまでの数のすべての組み合わせを提供します。これは最大で2Nです。

于 2013-03-26T05:56:53.940 に答える
1

総当たり攻撃します。Nが8に制限されている場合、サブセットの総数は2 ^ 8であり、これは256にすぎません。これらは理由のために制約を与えます。

セットの包含は、各要素がセット内またはセット外のいずれかにあるバイナリ文字列として表すことができます。次に、バイナリ文字列（単純に整数として表すことができます）をインクリメントし、ビット単位の＆演算子を使用して、セットに含まれる要素と含まれない要素を判別します。2 ^ Nまでカウントすると、すべての可能なサブセットを通過したことがわかります。

于 2013-03-26T05:38:47.457 に答える
1

それを行う最良の方法は、動的計画法のアプローチを使用することです。ただし、動的計画法は、質問で述べたように、サブセット和が存在するかどうかに答えるだけです。

動的計画法により、バックトラックによってすべての解を出力できます。ただし、すべての有効な組み合わせを生成するための全体的な時間計算量は2^nのままです。

したがって、2^nよりも優れたアルゴリズムはほぼ不可能です。

UPD：@Knootheからコメント：horowitz-sahniのアルゴリズムを変更して、可能なすべてのサブセットを列挙できMます。合計がに等しいそのようなセットがある場合S、全体的な時間計算量は次のようになります。O(N * 2^(N/2) + MN)

于 2013-03-26T05:40:30.697 に答える