算法将数组分割成平衡的和p子阵 [英] Algorithm to split an array into P subarrays of balanced sum

问题描述

我有长度为N的大阵，让我们这样说：

I have an big array of length N, let's say something like:

2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1

我需要分割这个数组为P子阵列（在本例中， P = 4 将是合理的），使得该元件的每个子阵列的总和作为尽可能接近西格玛，存在：

I need to split this array into P subarrays (in this example, P=4 would be reasonable), such that the sum of the elements in each subarray is as close as possible to sigma, being:

sigma=(sum of all elements in original array)/P

在这个例子中，差= 15 。

有关清楚起见，一个可能的结果将是：

For the sake of clarity, one possible result would be:

2 4 6    7 6 3 3   3 4 3 4    4 4 3 3 1
(sums: 12,19,14,15)

我已经写了总部设在我会怎么做师用手工一个很天真的算法，但我不知道该怎么征收的条件下，一个部门，其数额为（14,14,14,14,19）是不如一个是（15,14,16,14,16）。

I have written a very naive algorithm based in how I would do the divisions by hand, but I don't know how to impose the condition that a division whose sums are (14,14,14,14,19) is worse than one that is (15,14,16,14,16).

感谢你在前进。

推荐答案

如果我没有记错这里，还有一个方法是动态规划。

If I am not mistaken here, one more approach is dynamic programming.

您可以定义的 P 的[ POS 的 N 的]作为最小的惩罚累计达定位的 POS 如果的 N 的创建子阵列。显然，有一些位置pos这样

You can define P[ pos, n ] as the smallest possible "penalty" accumulated up to position pos if n subarrays were created. Obviously there is some position pos' such that

P [POS'中，n-1] +惩罚（位置'，正）= P [POS，n]的

P[pos', n-1] + penalty(pos', pos) = P[pos, n]

您可以只减少了POS'= 1..pos。

You can just minimize over pos' = 1..pos.

天真的实施将在O（N ^ 2 * M），运行在N - 原数组的大小和M - 分割数

The naive implementation will run in O(N^2 * M), where N - size of the original array and M - number of divisions.

这篇关于算法将数组分割成平衡的和p子阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！