1

我正在阅读此http://www.cas.mcmaster.ca/~terlaky/4-6TD3/slides/DP/DP.pdf并想知道是否存在对分区问题具有更好时间复杂度的解决方案。

从链接：

“假设给定一个非负数 {s1,...,sn} 和整数 k 的排列 S。如何将S 分成 k 个或更少的范围，以最小化所有范围内的最大和？

例如

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

k=3

通过将 S 切割成这 3 个范围，最大范围 (8,9) 的总和为 17，这是可能的最小值。

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

链接中建议的算法在 O(kn^2) 中运行并使用 O(kn) 空间。有没有更高效的算法？

4

1 回答 1

1

好吧，显然这是因为“离题”而被关闭！？但它现在已经备份，所以无论如何，我发现解决方案是二进制搜索答案。抱歉，我忘记了其中一个限制条件是所有整数的总和不会超过 2^64。所以让C =所有整数的累积和。然后我们可以使用二进制搜索答案

bool isPossible(int x)

如果可以将 S 划分为 k 个分区且最大分区总和小于 X，则返回 true 的函数。 isPossible(int x) 可以在 O(n) 中完成（通过从左到右添加所有内容，如果它超过 x，则生成一个新分区）。所以总运行时间是 O(n*log(s))。

于 2013-02-07T07:21:21.843 回答