目標を達成するために、セットから最大 1 つの要素を除外できます。例：-
N=3
与えられた数字は = 1,2,5
そう、
セット 1 は :- [1]
セット 2 は :- [2]
どちらのグループにも属さなくても差が小さくなる可能性があるため、5 を除外しました。
N=4
数字 = 1,2,2,5
Set1 = [1,2,2]
セット 2 = [5]
これに最適なアルゴリズムは何ですか? これが NP 完全問題であることはわかっています。そして、力ずくで正しい解決策が得られると思いますが、可能であればアルゴリズムが必要です。
これが NP 完全問題であることはわかっています。
正確ではありませんが、パーティション最適化問題は NP 困難であることが知られています。
そして、力ずくで正しい解決策が得られると思いますが、可能であればアルゴリズムが必要です。
NP困難とは、ブルートフォース法よりも優れたパフォーマンスを発揮する（解を決定するための）既知のアルゴリズムがないことを意味します。
したがって、おそらく近似値が必要になりますが、どれがニーズに合っているかは、あなただけが知ることができます.
これに最適なアルゴリズムは何ですか?
「最高」を定義します。
これは、整数のセットを合計が等しい、または可能な限り等しい 2 つのサブセットに分割するという有名な問題のバリエーションです。ただし、提起した問題はさらに困難です。さらに、元のセットから 1 つの要素を削除したすべての組み合わせをチェックする必要があります。
元の問題は NP 完全であるため、これも NP 完全です (実際、Bergi の回答で正しく言及されているように、これは NP 困難でさえある問題の最適化バージョンです)。良いニュースは、このより難しいバージョンでも、ほとんどの場合、貪欲なアプローチで満足のいく答えが得られることです。戦略は次のとおりです。元のセットから最大の要素を取得し、それらを 1 番目と 2 番目のサブセットにそれぞれ 1 つずつ配置します。元のセットの他のすべての要素を、合計がより小さいサブセットに入れ、すべての要素を選択するまで手順を繰り返します。
最良の結果を得るには、元のセットの N 個のサブセットすべてに対してこの手順を繰り返す必要があります。ここでは、インデックス 1、2、...、N の要素を削除して各サブセットを取得します。これが、この問題をさらに難しくしている理由です。
より高度なアプローチに興味がある場合は、Karmarkar-Karp 差分アルゴリズムをご覧ください。
以下も参照してください。