c - サブセットの個別の和の数

Question

私はNのセットを持っています。N> 3の異なる整数であり、問​​題は、指定されたセットの3つのサブセットのすべての異なる合計を見つけることです。3 サブセットは、カーディナリティが 3 のサブセットです。

ばかげた方法は、考えられるすべての合計に対して 3 次検索を実行してから、すべての重複を分類することであることを知っています。これを行うより効率的な方法はありますか？私はCでプログラミングしています。

編集:要素の数が増えたとしたら、一般的なより高速なアルゴリズムを知りたいと思いました。

Answer 1

重複した合計が多数あると思われる場合は、最初にすべての個別の 2 サブセットの合計を計算し、見つかった個別の 2 サブセットの合計ごとに、どのペアを見つけて合計が得られたかを追跡できます。すべての数値が異なる場合、同じ合計を与える別のペアを見つけた場合は、合計を「複数」としてマークする必要があり、必要に応じて保存していたペアを削除できます。これで、2 サブセット合計のセットができました。各合計には、単一のペアが格納されているか、「複数」とマークされています。各 2 サブセットの合計について、「複数」とマークされている場合は、元のセットのすべての数値を反復処理し、各数値を 2 サブセットの合計に追加して形成できるすべての 3 サブセットの合計を記録します。それ以外の場合、2 サブセットの合計が「複数」とマークされていない場合 それに関連付けられたペア (a,b) がある場合、元の数値セットを反復処理するときに a と b をスキップすることを除いて、同じことを行います。これは、すべての個別の 3 サブセット合計を取得する方法です。n 個の数値があり、それらが N 個の別個の 2 サブセット合計を作成する場合、ハッシュ テーブルを使用してアルゴリズムの 2 段階で重複を検出すると、このアプローチの複雑さは O(nN) になり、ブルートよりもはるかに優れている可能性があります。特にかなり密集した整数のセットがある場合は、O(n^3 log n) を強制します。

Answer 2

動的計画法を使用すると、 の個別の合計の数を見つけることができますO(n*MAX)。ここMAXで、 は配列の最大値です。

再帰関数を見てみましょう。

f(W,n,i) = f(W,n-1,i) OR (i != 0 ? f(W-item(n),n-1,i-1) : false)
f(0,0,0) = true
f(W,n,0) = false (W != 0)
f(W,0,i) = false (W != 0)
f(W,n,i) = false (W < 0)
(I have a feeling I forgot another failing base clause, so make sure if I didn't)

ここで、動的計画法を使用してこのボトムアップを まで構築するとW=3*MAX、答えは基本的Wにそれらの の異なる の数になりますf(W,n,3) == true。

テーブルの構築は になります。目的の合計を与えるO(MAX*3 * n * 3) = O(MAX*n)個別の の数をカウントする後処理段階はです。したがって、解決策は残ります。WO(MAX)O(MAX * n)