3

我有一个 N 个正整数的集合，每个正整数都以一个（相对较小的）常数 C 为界。我想找到这些数字的一个子集，其中最小的总和大于（或等于）一个值 K。

涉及的数字不是很大（<100），但即使在最坏的情况下我也需要良好的性能。我想也许我可以让 Pisinger 的动态规划算法适应这项任务；它在 O(NC) 时间内运行，我碰巧满足有界正数的要求。

[编辑]：数字未排序，可能有重复。

但是，我对算法的理解不够好，无法自己做到这一点。事实上，我什至不确定它所基于的假设是否仍然成立......

- 是否可以根据我的需要调整该算法？

- 或者我可以使用另一种同样有效的线性算法吗？

- 谁能提供伪代码或详细解释？

谢谢。

链接到我正在调查的子集和代码： Pisinger 的子集和算法的快速解决方案

（抱歉，如果措辞/格式/等不好。我还是 StackOverflow 的新手......）

4

2 回答 2

4

Pisinger 算法为您提供小于或等于背包容量的最大总和。要解决您的问题，请使用 Pisinger 找出不要放入子集中的内容。形式上，设项目为 w_1, ..., w_n，最小值为 K。将 w_1, ..., w_n 和 w_1 + ... + w_n - K 给 Pisinger，然后取出 Pisinger 没有的所有项目。

于 2013-06-19T00:25:55.203 回答
0

一种解决方案是：

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 bound），所以运行时间是O(N^2)，空间是O(N)。您可以使用长度为 NC 的位数组作为 T 的后备存储。

于 2013-06-18T03:39:45.690 回答