将列表分为两个等份算法

本文介绍了将列表分为两个等份算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

相关问题:

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

• 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，同时尝试使这些部分的总和尽可能相等.

Let's assume I have a list, which contains exactly 2k elements. Now, I'm willing to split it into two parts, where each part has a length of k while trying to make the sum of the parts as equal as possible.

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

Quick example: [3, 4, 4, 1, 2, 1] might be splitted to [1, 4, 3] and [1, 2, 4] and the sum difference will be 1

现在-如果零件可以具有任意长度，则这是 分区问题的一种变体 ，我们知道这是NP-Complete.

Now - if the parts can have arbitrary lengths, this is a variation of the Partition problem and we know that's it's weakly NP-Complete.

但是将列表分成相等部分的限制(假设总是k和2k)是否可以在多项式时间内解决此问题?对此有任何证据(或者仍然是NP的证据方案)?

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)?

推荐答案

它仍然是NP完整的.通过将PP(您的分区问题的完整变体)减少为QPP(等分分区问题)来进行证明:

It is still NP complete. Proof by reduction of PP (your full variation of the Partition problem) to QPP (equal parts partition problem):

获取任意长度为k的列表，以及其他所有均为零的k元素.

Take an arbitrary list of length k plus additional k elements all valued as zero.

我们需要根据PP找到性能最佳的分区.让我们使用针对QPP的算法找到一个，而忽略所有其他k零元素.零移位不会影响此分区或任何竞争分区，因此，它仍然是长度为k的任意列表的性能最好的无限制分区之一.

We need to find the best performing partition in terms of PP. Let us find one using an algorithm for QPP and forget about all the additional k zero elements. Shifting zeroes around cannot affect this or any competing partition, so this is still one of the best performing unrestricted partitions of the arbitrary list of length k.