3

これが私の問題です。

2N 個の要素を持つ並べ替えられていない配列が 1 つあります。これらの要素はすべて正の整数です。Q: この配列を 2 つの N 配列に分割する方法と、2 つの配列の合計が互いに最も近くなければならない

1つの直感的な考えは、

  1. この配列を a1< a2 < a3< ...< a2N にソートし、
  2. それらを 2 つのサブ配列 a1 a3 a5 ... a(2N-1) と [a2,a4,...a2N] に分割し、各配列で 2 つの数値を切り替え、2 つの間の最小のものを見つける util をループし続けます配列。

しかし、この方法では、最適なものを見つけることはできません。

4

2 に答える 2

5

これはPartition Problemであり、困難です (つまり、NP 完全)。

とはいえ、これを実装する必要がある場合は、提案する貪欲なアルゴリズムが適切な仕事をします。最初のリストから 1、2 番目のリストから 2、最初のリストから 2、...、2 番目のリストから 1 を取得することで、1 つのリストが常に他のリストよりも小さいとは限らないことを確認することで、少し改善できます。

A = [a1, a4, a5, a8, a9, ..., a(n-2), a(n-1)]
B = [a2, a3, a6, a7, ..., a(n-4), a(n-3), an]

これで常に最適なソリューションが得られるとは限りませんが、ほとんどの場合はこれで十分です。また、「最初に行く」という偏見も防ぎます。

于 2012-09-12T01:50:20.397 に答える
2

部分和問題を調べる必要があります。あなたの場合、S/2 のサブセットの合計を求めています。ここで、S は完全な合計です。最もよく知られている整数の場合にそれを行う単純な動的計画法アルゴリズムがあります。残念ながら、これは疑似多項式時間です。これは、実行時間が要素のサイズの多項式であることを意味します。これにより、通常の意味では指数関数的な時間になりますが、要素が大きすぎない場合は問題なく機能します。

サブセット合計動的プログラムは、正確に N 個の要素 e[i] の要件を強制するために少し変更する必要があります。Q(i, s, n) は、1 から i までの合計で s になる要素から選択され、正確に n<=i 要素を含むサブセットが存在する場合に真とします。

それで

Q(i, s, n) = Q(i - 1, s, n) または Q(i - 1, s - e[i], n - 1)

基本ケースでは、要素をまったく使用しない場合、サブセット内の合計と必要な数は両方ともゼロでなければならず、そうでない場合、Q は false になります。

Q(0, 0, 0) = true、それ以外の場合 Q(0, _, _) は false。

答えを得るには、真の値が見つかるまで、Q(2N, k, N)、k = 天井 (S/2)、天井 (S/2)-1、... の DP テーブルを計算します。

この問題はサブセット和に十分近いため、NP 困難になることに注意してください。これは、真の多項式時間アルゴリズム (並べ替えの提案など) が最適性の近似値になることを意味します。もちろん、現実的な目的にはそれで十分かもしれません。

于 2012-09-12T01:01:49.310 に答える