NP完全なパーティション問題のバリエーションである問題があります。これは最適化の問題であり、決定の問題ではありません。
問題: 和の差が最小になるように数のリストを 2 つの部分集合に分割し、2 つの部分集合を見つけます。偶数の場合n、サイズは でn/2、奇数の場合はfloor[n/2]とceil[n/2]です。
疑似多項式時間 DP アルゴリズムが正確な解に最適であると仮定すると、これを解決するためにどのように変更できますか? そして、これを解決するための最良の近似アルゴリズムは何でしょうか?