线性算法寻找超过阈值的最小子集和

Question

我有一个包含N个正整数的集合，每个数字都被一个（相对较小的）常量C限制。我想找到一个子集，使得它们的和最小且大于（或等于）一个值K。

这些数字并不是特别大（<100），但我需要在最坏情况下也能获得良好的性能。我认为我可以将Pisinger的动态规划算法适应到这个任务上；它的运行时间为O（NC），而我的要求是有界的正数。

[编辑]：这些数字没有排序，可能存在重复。

然而，我不太了解该算法，无法自己完成。事实上，我甚至不确定它所基于的假设是否仍然成立...

- 是否可能将此算法适应到我的需求中？

- 或者是否有另一个线性算法可以使用，效率类似？

- 任何人都可以提供伪代码或详细说明吗？

谢谢。

链接到我正在调查的Subset-Sum代码： Fast solution to Subset sum algorithm by Pisinger （如果这样表述/格式等不好，请谅解。我还是StackOverflow的新手...）

- Athena

---

这不是背包问题的变体吗？ - phoeagon

是的。具体来说，它是Subset-Sum的一个变种（Subset-Sum本身是Knapsack问题的一个特例）。 - Athena

为了以后的参考，请尽量避免在存在重复项时使用“set”这个术语。“collection”会是一个更好的术语。 - Nathan Henkel

Answer 1

Pisinger算法可以给出小于或等于背包容量的最大总和。为了解决您的问题，请使用Pisinger算法来确定不放入子集的物品。形式化地，让物品为w_1，...，w_n，最小值为K。将w_1，...，w_n和w_1 + ... + w_n-K传递给Pisinger，然后选择每个Pisinger没有选择的物品。

- David Eisenstat

---

我确实考虑过执行相反的操作，就像你所说的那样，但这将是O(n(n-k)) = O(n^2)，而不是线性的。 - Athena

@Athena Pisinger的运行时间为O（物品数量*最大物品数），不取决于背包大小或最优解存储的物品数量。 - David Eisenstat

啊，你说得对！（我把我的常量搞混了。）这对我的目的很有用。非常感谢！ - Athena

Answer 2

一个解决方案是：

T = {0}

for x in V
   for t in T
       T.insert(x+t)

for i in K to max(T)
   if (T.contains(i))
       return i

fail

这将给你子集的大小，但你可以适应输出成员。

T 的最大大小是 O(N)（由于 C 限制），因此运行时间为 O(N^2)，空间为 O(N)。您可以使用长度为 NC 的位数组作为 T 的后备存储。

- Andrew Tomazos

---

我认为O(N^2)算法不应被视为线性算法。 - Mark Ransom

哦，我没有注意到标题，我以为我们只是在尝试多项式时间。 - Andrew Tomazos

我会澄清问题，以表明它是“线性的”。无论如何，谢谢。 - Athena