algorithm - 将列表分成两等份算法

Question

Related questions:

• Algorithm to Divide a list of numbers into 2 equal sum lists
• divide list in two parts that their sum closest to each other

假设我有一个列表，其中恰好包含 2k 元素。现在，我愿意将它分成两部分，其中每个部分的长度为 k，同时尝试使部分的总和尽可能相等。

简单示例: [3, 4, 4, 1, 2, 1] 可能会拆分为 [1, 4, 3] 和 [1, 2, 4] 和之差将是 1

现在 - 如果零件可以有任意长度，这是 Partition problem 的变体我们知道它是弱 NP-Complete。

But does the restriction about splitting the list into equal parts (let's say it's always k and 2k) make this problem solvable in polynomial time? Any proofs to that (or a proof scheme for the fact that it's still NP)?

Answer 1

它仍然是 NP 完整的。通过将 PP(分区问题的完整变体)简化为 QPP(等份分区问题)来证明:

取一个长度为 k 的任意列表加上额外的 k 元素，所有元素的值为零。

我们需要根据PP 找到性能最佳的分区。让我们找到一个使用 QPP 的算法并忘记所有额外的 k 零元素。移动零不会影响此分区或任何竞争分区，因此这仍然是任意长度 k 列表中性能最好的无限制分区之一。