最小最大连续ķ分区更快的算法 [英] faster algorithms for minimum maximum contiguous k partition

问题描述

我在读这 HTTP：// WWW .cas.mcmaster.ca /〜terlaky / 4-6TD3 /幻灯片/ DP / DP.pdf ，并想知道是否存在更好的时间复杂度的解决方案的划分问题。

I was reading this http://www.cas.mcmaster.ca/~terlaky/4-6TD3/slides/DP/DP.pdf and would like to know if there exists a solution with better time complexity to the partition problem.

从链接：

假设的非负数一个给定的排列小号   {S1，...，SN}和一个整数k。如何削减 s转换k或更少的范围内，   以便最小化在所有范围内的最大总和？

"Suppose a given arrangement S of non-negative numbers {s1,...,sn} and an integer k. How to cut S into k or fewer ranges, so as to minimize the maximum sum over all the ranges?"

例如。

S = 1,2,3,4,5,6,7,8,9

S = 1,2,3,4,5,6,7,8,9

K = 3

通过切割小号到这些3个范围，最大范围的总和（8,9）是17，这是可能的最小值。

By cutting S into these 3 ranges, the sum of the maximum range (8,9) is 17, which is the minimum possible.

1,2,3,4,5 | 6,7 | 8,9

1,2,3,4,5|6,7|8,9

在连结提出的算法在O（KN ^ 2）运行，并使用O（KN）的空间。是否有更有效的算法？

The algorithm suggested in the link runs in O(kn^2) and uses O(kn) space. Are there more efficient algorithms?

推荐答案

好了，所以显然这是关闭被题外话！？ 但它的备份现在如此，无论如何，我找到了解决方案，为二进制搜索答案。对不起，我忘了的制约因素之一是，所有的整数的总和不会超过2 ^ 64。因此，让C =所有整数的累计总和。然后，我们可以使用二进制搜索答案一

Ok so apparently this was closed for being "off-topic"!? But it's back up now so anyway, I found the solution to be binary searching the answer. Sorry I forgot one of the constraints was that the sum of all the integers would not exceed 2^64. So let C = cumulative sum of all integers. Then we can binary search for the answer using a

布尔isPossible（INT X）

功能是否可以划分小号成k分区与最大分区总和小于十isPossible（中间体X）的返回true可以在O（n）的进行（通过添加了从左至右，如果它超过x可保证新的分区）。因此，总运行时间为O（n *日志（S））。

function which returns true if it is possible to divide S into k partitions with maximum partition sum less than X. isPossible(int x) can be done in O(n) (by adding everything from left to right and if it exceeds x make a new partition). So the total running time is O(n*log(s)).

这篇关于最小最大连续ķ分区更快的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！