algorithm - 如何划分列表的方法

Question

假设我有 n 个值为 x[i] 的元素.让所有值的总和表示为 X，我们强制每个元素为 x[i] <= X/2。 .现在给出数组 x[] ，如何将它分成两组(至少大小为 1)，使每组的总和小于或等于 2X/3？

我被这个问题困扰了一段时间。我发现在某些情况下这实际上是不可能的，但除此之外我只研究了贪婪的方法:把一个元素 x[i]进入具有最小累积和的分区。关于如何解决这个问题有什么想法吗？

Answer 1

确定找到反例了吗？我的数学可能是错误的，但似乎不可能构建这样一个列表。让我们注意，对于三个元素的列表 a <= b <= c ，我们可以将它们分区为 [a, b], [c] .这是因为 a + b大于总和的 2/3，我们有 (a + b) * 3 > 2 * (a + b + c)或 a + b > 2 * c , 这意味着 a和/或 b需要大于 c .

考虑到这一点，我们将数字分为三个箱子，每个箱子的总和小于 N/2 .请注意，如果我们有四个元素 a <= b <= c <= d , 我们可以将它们划分为 [a, b], [c], [d] .重复之前的逻辑，对于 a + b大于 N/2 , 我们需要 (a + b) * 2 > (a + b + c + d)或 a + b > c + d ，这意味着 a和/或 b必须大于 c .

我们可以从这里无限期地重复这个逻辑。以我们的列表为x , 对于 a + b大于 N/2 , 我们需要 (a + b) * 2 > sum(x) ，这对于带有 2 的列表是不可能的或大于 a 的更多元素和 b (所有长度为 4 或以上的列表都是这种情况)。

应用这种递归逻辑，我们可以从 n 向上构建箱子到三个箱子，将它们视为 a, b, c第一段中的数字，并以此方式构建我们的答案。

从算法上讲，创建一组节点，其中包含数组中的每个元素(作为长度为 1 的列表)和总和(暂时等于元素本身)。将这些插入到最小堆中，以总和作为键。弹出最小两个，合并它们(连接元素列表，添加总和)并推回最小堆。冲洗并重复，直到堆中有两个节点。它们现在包含您的解决方案。