algorithm - 恰好 k 个元素的最小非连续序列

Question

我遇到的问题可以简化为:

Given an array of N positive numbers, find the non-contiguous sequence of exactly K elements with the minimal sum.

Ok-ish: report the sum only. Bonus: the picked elements can be identified (at least one set of indices, if many can realize the same sum).

(通俗地说:从 N 个值中挑选任意 K 个 非相邻 元素，使它们的总和最小)

当然，2*K <= N+1 (否则无解)，问题对正/负不敏感(只需用 MIN=min(A...) 移动数组值，然后将 K*MIN 添加回答案)。

到目前为止我得到了什么(天真的方法):

1. 选择K+2最接近最小值的索引。我不确定，因为 K=2这似乎是涵盖所有特定情况所必需的，但我不知道它是否需要/足够 K>2 **
2. 根据非连续性标准，从上一步产生的索引值中强制计算最小总和 - 如果我是对的并且 K+2够了，我可以暴力破解 (K+1)*(K+2)解决方案空间，但正如我所说。我不确定 K+2足够 K>2 (如果事实上 2*K 点是必要的，那么暴力破解就会消失——二项式系数 C(2*K, K) 增长得非常快)

关于如何以最小的时间/空间复杂度完成此操作的任何巧妙想法？

** K=2 ，一个重要的例子，其中需要 4 个最接近绝对最小值的值来选择目标总和 [4,1,0,1,4,3,4] - 不能使用 0建立最小总和的值(value)，因为它打破了不连续的标准。

PS - 如果您想展示代码片段，C/C++ 和/或 Java 将不胜感激，但任何具有良好语法或伪代码的语言都可以_{(我认为“良好语法”不包括 Perl，不不是吗？)}

Answer 1

假设输入数字存储在数组 a[N] 中

通用方法是 DP:f(n, k) = min(f(n-1, k), f(n-2, k-1)+a[n])

它需要 O(N*K) 时间并且有 2 个选项:

• 对于惰性回溯递归求解O(N*K)空间
• 对于正向循环的O(K)空间

在大K的特殊情况下还有另一种可能性:

• 使用递归回溯
• 使用 map(n, map(k, pair(answer, list(answer indexes)))) 代替 N*K 大小的辅助数组
• 保存这个答案的答案和索引列表
• 如果 k>N/2 立即返回 MAX_INT

这样对于 K~=N/2，您的时间将少于 O(NK)，类似于 O(Nlog(N))。对于较小的 K，它将增加到 O(N*log(N)Klog(K))，因此在一般方法或特殊情况算法之间做出决定很重要。