algorithm - 整数のペアを割り当てる

Question

この問題を解決する方法：
N組の整数が与えられます。整数の各ペアについて、Aに割り当てられた整数の合計とBに割り当てられた整数の合計の差が最小になるように、一方の整数をAに割り当て、もう一方をBに割り当てる必要があります。
O（2 ^ N）より良いものは考えられません。
貪欲だと思いましたが、必ずしも最適な結果が得られるとは限りません。

Answer 1

問題を次のように変換します。

与えられたもの：非負の整数のシーケンス（元のペア間の絶対差）
問題：各サブセットの要素の合計の絶対差を最小化するように、整数を2つのセットに分割します。

これは、NP完全である平衡分割問題です。2つの問題は同等です。つまり、バランス分割問題を問題に変換できます。シーケンスの要素n _iごとに、整数のペア（n _i、0）を関連付けます。^{したがって、O（2 N} ）よりもうまくいくことはありません。

問題：シーケンスの合計の絶対値が最小になるように、各整数に符号（プラス/マイナス）を割り当てます。

^*シーケンスを最初に降順でソートすると、欲張りアルゴリズムが最適な結果をもたらすと思います。これはO（N log N）アルゴリズムになります。

（^*）間違っている場合は、反例を投稿してください。

Answer 2

ペアを（A_0、B_0）、...、（A_n、B_n）とします。D_i = |A_i-B_i|とします。次に、問題は、合計を最小化するためにD_iの符号を選択​​することと同じです。これは、合計が合計の半分になるD_iのサブセットを見つけることと同じです。これは、NP完全であるサブセット和と同等です。したがって、2^nよりもうまくいくことはありません。

ただし、数値が小さい場合は、動的計画法のアプローチを試すことができます。D_0、..、D_iを使用して合計nになるサブセットを選択できる場合は、DP[i][n]が真になります。DP [0] [0]が真であるところから始め、DP [i] [n]が真であるか、DP [i] [nD [i + 1]]が真である場合、DP [i +1][n]は真です。本当。この解はO（n *（可能な最大の合計））です。