algorithm - 用于将数字区域划分为具有最相等总和的分区的贪婪算法？

Question

假设我们有一个数字序列，我们有 X 个部分将其分为:

1, 4, 7, 9, 3, 11, 10

如果我们有 3 个部分，最佳答案是:

[1, 4, 7][9, 3][11, 10]或[1, 4, 7, 9][3, 11][10]

因为最大和=21。这是最好的情况。 (我想，我是手工完成的)。

我们希望每个部分尽可能平等。如何才能做到这一点？我对算法的第一次尝试是找到最高的 X 值(9、11、10)，并以此为基础划分区域。这在如下示例中不起作用，因为其中一个区域将不包含集合中的最高值之​​一:

3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1,

再次使用 X=3 个部分，最佳答案:

[3, 2][2, 1, 1, 1][1, 1, 1, 1, 1]

当然，我可以暴力破解所有可能的组合，但有一种更有效的方法可以做到这一点。但我找不到它。

Answer 1

这正是 @rta3tayt32yaa32y 所说的线性分区问题。

如果你真的像你的主题所说的那样是一个贪心算法，这将是一个近似值，那么只需将元素的总和除以 X。称此为 D。在你从列表的开始到结束工作时保持累加和。每次sum达到D以上，就把之前的元素做一个section，删掉，重新开始sum。如果序列为 1、4、7、9、3、11、10，则总和为 45。对于 X=3，我们有 D=15。所以第一部分是 [1, 4, 7] 因为加 9 会使总和为 21。接下来是 [9, 3] 因为加 11 会使总和为 22。最后留下 [11,10]。

要找到准确的答案，您需要一个动态程序。这has already been extensively discussed here所以我不会重复。这个问题比较困惑，但是@Óscar López 的回答很好。