2つの配列の要素の同一の合計

Question

同じ長さの2つの整数の配列v1とv2があります。私はv1の要素の最大部分集合を求め、その合計はv2の対応する要素のものと同じです。これは私が探していますサブセットになるので、例えば、両方の配列に

v1 = [1 2 3 1] 
v2 = [2 3 1 2] 

第二、第三及び第四の要素の和である6をしましょう。

これを計算する方法はありますか？

ありがとうございます。 チェーザレ

Answer 1

デルタを計算すると、問題はsubset sum problemに減少します。言い換えれば、各要素が2つの入力配列内の対応する要素間の差である第3の配列を作成します。入力配列v1とv2所与例えば

、相違点を含ん第3のアレイv3作成：

 0 1 2 3 <-- index into the array 
v1 = [ 1 2 3 1] 
v2 = [ 2 3 1 2] 
v3 = [-1 -1 2 -1] 

を次に0に追加v3における任意のサブセットは、溶液です。この例では、解は、{0,1,2},{0,2,3}および{1,2,3}のインデックスの組で表されます。