algorithm - 给定一组整数 L 和一个整数 K，选择 L 的最小子集 S，使得 SUM(S) >= K

Question

问题对于标题来说有点太长了，所以这里是确切的定义:

输入

整数集，L

整数，K

输出

L 的一个子集使得:

• 子集之和 >= K
• 子集中的元素数量最少
• 如果多个子集都满足上述条件，则优先选择最大值最小的子集。
• 如果多个子集仍然并列，则首选总和最低的子集。

例如

输入

L = { 4, 2, 3, 1 }

K = 5

前两个条件将产生 {4, 2}、{4, 3}、{4, 1} 和 {2, 3}。我们更喜欢 {2, 3}，因为它的最大值 (3) 是其中最小的。

如果没有满足条件的子集，则返回 null 或抛出异常。

我有点担心这个问题与子集和问题太相关，可能是 NP 完全问题。

Answer 1

解决方案可能如下:

(1) 对L排序得到l_1, l_2, ..., l_n , 与 l_1 > l_2 > ... > l_n .

(2) 对于 k=1,2,...,n , 检查是否 (l_1+...+l_k) >= K , 为最小的 k 停止。

现在您拥有了满足第一个条件所需的最少元素数量，以及一个示例集 {l_1,...,l_k}.

(3) 现在我们要找到一个有k个元素的集合来满足其余的。你可以例如从总结开始

l_n + l_(n-1) + ... + l_(n-k), then 
l_(n+1) + l_n + ... + l_(n-k+1), then 
l_(n+2) + l_n + ... + l_(n-k+2), ...

并在其中一个总和超过或等于 K 时停止。

(1) 可以在 O(n*log(n)) 中完成时间，(2) 可以在 O(n) 中完成时间。(3) 可以在O(n*k) = O(n^2)中完成时间。然而，这可以通过使用“望远镜总和”来改进:

• 计算 x := l_n + l_(n-1) + ... + l_(n-k) .
• 如果x < K , 然后计算 x := x - l_n + l_(n-k+1)
• 如果x < K , 然后计算 x := x - l_(n-1) + l_(n-k+2)等

所以 (3) 可以在 O(n) 中完成, 看起来。

所以总的来说，O(n*log(n))似乎可以完成这项任务。