将数组分成 n 部分的算法

Question

在最近的校园 Facebook 面试中，我要求将一个数组分成 3 个相等的部分，使得每个数组中的总和大致等于 sum/3。

我的方法
1 .排序数组
2。将数组[k] (k=0) 填充到 (array[k]<=sum/3)
3。之后增加 k 并为数组 [k] 重复上述步骤

是否有更好的算法或者它是 NP 难题

Answer 1

这是分区问题的一个变体(详见 http://en.wikipedia.org/wiki/Partition_problem)。事实上，这个问题的解决方案可以解决那个问题(取一个数组，用 0 填充，然后解决这个问题)所以这个问题是 NP 难的。

有一种伪多项式的动态规划方法。对于从 0 到数组大小的每个 i，您要跟踪子数组当前大小及其当前总和的所有可能组合。只要数组子集的可能总和数量有限，它的运行速度就可以接受。

我建议的解决方案是只追求“足够好”的亲密关系。首先让我们考虑所有值为正的更简单的问题。然后按值降序排序。把那个数组分成三份。始终将三元组中的最大者与总和最小的那个相加，将最小的与最大的相加，将中间的与中间的相加，从而构建三个子集。你最终会平分数组，差值不会超过第三小的元素的值。

对于一般情况，您可以分为正面和负面，对每个使用上述方法，然后暴力破解一组正数、一组负数和中间的少数剩余值的所有组合平分。