この質問に出くわしましたが、合理的な解決策が見つかりませんでした。サブ配列の合計の差が最小になるように、ソートされていない整数配列を 2 つの等しいサイズのサブ配列に分割するにはどうすればよいでしょうか。
例: 整数配列 a[N] (ソートされていない) が与えられた場合、配列を a1 と a2 に分割します。ここで、a1.length == a2.length は N/2 であり、(a1 のすべての数値の合計 - a2) のすべての数値の合計は最小でなければなりません。
簡単にするために、すべての数値が正であると仮定しましょう。ただし、繰り返しがある可能性があります。
これは変更によるパーティションの問題のケースであると他の人が言及していますが、より具体的には、これは実際には 2 台のマシンでの最小メイクスパンの問題の特殊なケースであることを指摘したいと思います。つまり、2 台のマシンの makespan 問題を解いて値mを取得すると、最小の差が得られます。2*m - sum(i : i in arr)
ウィキペディアの記事にあるように、問題は 2 台以上のマシンで NP 完全です。ただし、あなたの場合、一般的におおよその答えを提供するリストスケジューリングアルゴリズムは、増加しない順序でソートされたリストが与えられた場合、2マシンおよび3マシンの場合に最適であり、多項式時間です。