algorithm - リストを 2 つの等しい部分に分割するアルゴリズム

Question

関連する質問:

• 数値のリストを 2 つの等しい合計リストに分割するアルゴリズム
• リストを 2 つの部分に分割し、それらの合計が互いに最も近くなるようにします

2k正確に要素を含むリストがあるとしましょう。ここで、それを 2 つの部分に分割します。各部分の長さは ですが、部分kの合計ができるだけ等しくなるようにします。

簡単な例: [3, 4, 4, 1, 2, 1]に分割される可能性が[1, 4, 3] and [1, 2, 4]あり、差額の合計は1

ここで、パーツが任意の長さを持つことができる場合、これは分割問題のバリエーションであり、弱いことがわかっています。NP-Complete.

しかし、リストを等分に分割することに関する制限(常にkとであるとしましょう2k) は、この問題を多項式時間で解決できるようにしますか? それに対する証拠はありますか（またはそれがまだであるという事実の証明スキームNP）？

Answer 1

それはまだNP完了しています。PP（パーティション問題の完全なバリエーション）をQPP（等しい部分のパーティション問題）に減らすことによる証明：

長さの任意のリストにk加えて、kすべてゼロとして評価される追加の要素を取ります。

の観点から、最もパフォーマンスの高いパーティションを見つける必要がありますPP。のアルゴリズムを使用して1つを見つけ、追加のゼロ要素QPPをすべて忘れましょう。kゼロをシフトしても、このパーティションや競合するパーティションに影響を与えることはできないため、これは、任意の長さのリストの中で最もパフォーマンスの高い無制限のパーティションの1つですk。