python - 划分数组，使子数组最大值的总和最小化

问题描述

我只能想到一种蛮力的方法来解决这个问题。有兴趣看看 Algo SO 社区会想出什么。

给出一个 arra和一个整数x(1<x<=len(a))。在不对数组重新排序的情况下，将数组划分为 x 个子数组s1, s2....sx ，以便总和max(s1) + max(s2)....+ max(sx)是子数组总和的所有可能组合中的最小值（参见下面的示例）。返回一个具有 x-1 索引的数组，其中包含发生拆分的索引 i（不包括在内）a[0:i], a[i+1:i2], a[i2+1: i3].....a[ix:]。

例子：

a = [10,30,40,20,50]
x = 2
return = [1]

将索引 1 处的数组拆分为 [10] 和 [30,40,20,50]

将导致max([10]) + max([30,40,20,50]) = 60这是所有其他拆分数组的方法中的最小值。

其他可能的分裂 -

不能在索引 0 处拆分，因为那样只会产生 1 个数组和 x = 2
在索引 2 处拆分 = max([10,30]) + max([40,20,50]) = 80
在索引 3 处拆分将导致 90
在索引 4 处拆分将导致 90
不允许在索引 5 处拆分，因为那样只会产生 1 个数组和 x = 2

标签： pythonalgorithmsorting

解决方案

这是一个动态规划问题。

首先建立以下数据结构。

for each position in the array
    for each count of how many splits
        (current max, sum of maxes, position of last split)

例如，在您的问题中，数据结构如下所示：

[   # One group, no splits
    [(10, 10, 0)], # 2 groups, 1 split
    [(30, 30, 0), (30, 40, 1)],
    [(40, 40, 0), (40, 50, 1), (40, 80, 2)],
    [(40, 40, 0), (20, 50, 1), (20, 70, 3)],
    [(50, 50, 0), (50, 60, 1), (50, 100, 2)], # the choices are equal
]

这可以通过简单的双循环来创建。你从[[(a[0], a[0], 0)]]. 并且要弄清楚i, j条目，您必须查看在(i-1, j-1)条目之后开始一个新组或将当前元素添加到条目中的最后一个组(i-1, j)。

一旦你有了这个，从数组的最后一个位置和所需的分割数开始。数据结构告诉你最后一次分裂在哪里，你去那个位置然后向下一个分裂找到前一个分裂的地方。沿着那个饼干屑的轨迹往回走，你会发现所有的裂痕。

在您的示例中，(len(a), x)条目位于(4, 1)并且具有 value (50, 60, 1)。上一个条目是 at(1, 0)并且具有 value (10, 10, 0)。我们忽略边界处的分裂并得到[1]答案。

如果你想做x=3，那么你会从开始(50, 100, 2)，回到(40, 50, 1)，然后到(10, 10, 0)并得到答案[1, 2]。

python - 划分数组，使子数组最大值的总和最小化

问题描述

解决方案

推荐阅读