python - int 値を合計がほぼ等しくなければならない 2 つのリストに均等に分配する

Question

リストの int 値を、合計がほぼ等しくなければならない 2 つのリストに均等に分配したいと考えています。厳密に等しくない場合は、差を返す必要があります。

li=[5,8,13,27,14]
first_list=[27,8)
second_list=[14,13,5]
return sum(first_list)-sum(second_list) #3

Answer 1

これは、 NP完全であるパー​​ティション問題の最適化問題です。

既知の多項式の解はありませんが、いくつかのヒューリスティックと近似アルゴリズムがあります。

また、比較的小さい整数の場合、実行可能な動的計画法のソリューションがあります。または、入力（要素の数）が比較的小さい場合は、指数ブルートフォースソリューションを使用できます。