1

これが問題です：

同じ長さの2つの配列AとBがあります。次のように、それらを2つのグループPとQに分割する必要があります。（1）それらの差が最小化される。（2）A [i]がPまたはQのいずれかに入る場合、B[i]は別の中に入る必要があります。

実際の問題へのリンクは次のとおりです。http：//opc.iarcs.org.in/index.php/problems/EQGIFTS

これが私の論理です（実際の問​​題を解決するため）：

入力がabcdefgの場合、値のリストとa、b、c、d、e、fのインデックスはそれぞれ0、1、2、3、4、5です。

tがa、b、c、d、e、f、gのインデックスである場合、プログラムは次のようにtとiをチェックします。 = 1であり、iの値を1増やし、tの値を1減らします。

一致するものが見つかるとすぐに、両方のインデックスの値を交換し、[t-1]から始まる値を並べ替えます。結果の値のリストが出力になります。

このアルゴリズムの何が問題なのかはわかりませんが、すべてのテストケースで間違った答えが返されます。私はそれが動的計画法を使用して解決できること、そしてそれがパーティション問題のバリエーションであることを知っています。しかし、この問題を解決するためにパーティションアルゴリズムを変更する方法がわかりません。

4

1 に答える 1

3

問題をパーティションの問題に減らし ます。それぞれ
に3番目の配列を作成します。D[i] = B[i] - A[i]i

ここで、問題は配列上の古典的なパーティションの問題Dであり、そのDPソリューションを使用して疑似多項式時間ソリューションを作成できます。

正当性の証明：（ ）に
解がある場合、次のように選択され、選択されます（各インデックスはiまたはjにあります）。Dsum(D_1) = sum(D_2)i_1,...,i_kD_1j_1,...,j_mD_2

sum(D[i's]) = sum(D[j's])

構造から、それは意味します：

sum(B[i]-A[i]) = sum(B[j]-A[j]) (for each relevant i's,j's)

したがって：

sum(B[i's]) - sum(A[i's]) = sum (B[j's]) - sum(A[j's])

これから：

sum(B[i's]) + sum(A[j's]) = sum(B[j's]) + sum(A[i's])

それぞれの「インデックス」が両方の部分に割り当てられているので、これはまさに私たちが望んでいたことです。一方の部分はBを取得し、もう一方はAを取得します。
他の方向も同様です。

QED

問題の複雑さ：
問題は、単純な削減では依然としてNP困難です。

パーティション問題（S=[a_1,a_2,...,a_n]）のインスタンスが与えられた場合、この問題のインスタンスを作成します。

A=S, B=[0,...,0]

この問題を最適に解決するのと同じ解決策が、元のパーティションの問題に対して必要なパーティションになることは容易に理解できます。したがって、問題はNP困難です。

于 2012-10-29T16:51:49.990 に答える