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

Question

相关问题：

• 将数字列表划分为2个相等总和列表的算法
• 将列表分成两部分，它们的总和彼此最接近

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

快速示例： [3, 4, 4, 1, 2, 1]可能会拆分为[1, 4, 3] and [1, 2, 4]，总和差将是1

现在 - 如果部分可以有任意长度，这是分区问题的变体，我们知道这是弱NP-Complete.

但是关于将列表分成相等部分的限制（假设它总是kand 2k）是否使这个问题可以在多项式时间内解决？任何证明（或证明它仍然存在的证明方案NP）？

Answer 1

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

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

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