<p><strong>编辑:基于澄清的问题,这里有另一种算法。我仍然保留了下面的原始回复,以防相关。</strong></p>
<p>你可以用动态规划来解决这个问题。请注意,下面的代码没有针对速度进行优化,因为我认为这会使它太难理解。如果您仔细地实现它,您可以在<code>O(N * K)</code>中执行,其中<code>N</code>是<code>a</code>的长度,<code>K</code>是要划分到的集的数目。在</p>
<pre><code>a = [1,3,4,11,12,19,20,21]
S = []
K = 3
# memoize results in (len(a) + 1) by K array
memo_partitions = [[None for j in xrange(len(a) + 1)] for i in xrange(K + 1)]
def compute_cost(arr):
# this is the objective to be minimized
if len(arr) == 0:
return 0
return sum(arr[-1] - x for x in arr)
def compute_best_partition(k, n):
# computes the best partition of the first `n` elements of `a`
# into `k` parts
if n == 0:
return [[] for _ in xrange(k)], 0
if k == 1:
return [a[:n]], compute_cost(a[:n])
if memo_partitions[k][n] is not None:
return memo_partitions[k][n]
best_partition = [[] for _ in xrange(k - 1)] + [a[:n]]
best_cost = compute_cost(a[:n])
for i in xrange(1, n):
last_group = a[i:n]
additional_cost = compute_cost(last_group)
partition, cost = compute_best_partition(k - 1, i)
if cost + additional_cost < best_cost:
best_partition = partition[:]
best_partition.append(last_group)
best_cost = cost + additional_cost
memo_partitions[k][n] = (best_partition, best_cost)
return memo_partitions[k][n]
best_partition, cost = compute_best_partition(K, len(a))
print best_partition
</code></pre>
<p><strong>以下是原始回复。</strong></p>
<p>这里有两种方法可以满足您的需要。假设你的数字按升序排列</p>
^{pr2}$
<p>让<code>max_diff(S)</code>表示集合<code>S</code>的两个元素之间的最大差。我们想把这些数字分成<code>S[0], ... , S[k - 1]</code>,这样<code>max_diff(S[i])</code>就很小了。在</p>
<p>首先,假设我们试图最小化<code>max_diff(S[i])</code>的和。注意,<code>max_diff(S[i])</code>的和就是<code>a[n - 1] - a[0]</code>减去<code>S[i]</code>之间的“间隙”。因此,您只需找到<code>k - 1</code>中最大的<code>a[i + 1] - a[i]</code>,并排除这些。在python代码中</p>
<pre><code>a = [1,3,4,11,12,19,20,21]
S = []
k = 3
diffs = [(a[i + 1] - a[i], i) for i in xrange(len(a) - 1)]
diffs.sort()
best_cuts = [i for diff, i in diffs[-k:]]
best_cuts.sort()
last_cut = 0
for cut in best_cuts:
S.append(a[last_cut:cut + 1])
last_cut = cut + 1
S.append(a[last_cut:])
print S
</code></pre>
<p>或者,假设我们试图最小化<code>max_diff(S[i])</code>的最大值。然后,我们可以对可实现值进行二进制搜索。在代码中</p>
<pre><code>a = [1,3,4,11,12,19,20,21]
S = []
k = 3
best_partition = None
low, high = 0, max(a)
while low < high:
mid = (low + high) / 2
# try to get all max_diffs <= mid
full_partition = []
last_set = [a[0]]
for val in a[1:]:
if val > last_set[0] + mid:
full_partition.append(last_set)
last_set = [val]
else:
last_set.append(val)
full_partition.append(last_set)
if len(full_partition) > k:
low = mid + 1
else:
high = mid
best_partition = full_partition
S = best_partition
print S
</code></pre>