线性算法找到最小子集和超过阈值 [英] Linear algorithm to find minimum subset sum over a threshold
问题描述
我有一个N个正整数的集合，每个都由一个（相对较小的）常量C限定。我想找到这些数字的一个子集，其中最小和大于（或等于）一个值K。
涉及的数字并不是非常大（<100），但即使在最坏的情况下，我也需要良好的性能。我认为也许我可以适应Pisinger的动态规划算法来完成任务;它运行在O（NC）的时间，我碰巧满足有界，正数的要求。
：数字不排序，重复。
但是，我不理解算法足够自己这样做。事实上，我甚至不确定它的假设是否仍然保持...
- 是否有可能使这个算法适应我的需要？ p>
- 是否还有另一个可以使用的线性算法，效率类似？
- 任何人提供伪码或详细解释？
感谢。
链接到我正在调查的子集Sum代码：
Pisinger对Subset sum算法的快速求解
（如果这是不好的措辞/格式化等等，我还是新的StackOverflow ...）
Pisinger的算法给你最小的总和小于或等于背包的容量。为了解决你的问题，使用Pisinger找出<em>不是放入子集。形式上，让项目是w_1，...，w_n，最小值是K.给w_1，...，w_n和w_1 + ... + w_n-K到Pisinger，然后取每个Pisinger没有的项目。 / p>
I have a collection of N positive integers, each bounded by a (relatively small) constant C. I want to find a subset of these numbers with the smallest sum greater than (or equal to) a value K.
The numbers involved aren't terribly large (<100), but I need good performance even in the worst case. I thought maybe I could adapt Pisinger's dynamic programming algorithm to the task; it runs in O(NC) time, and I happen to meet the requirements of bounded, positive numbers.
[Edit]: The numbers are not sorted and there may be duplicates.
However, I don't understand the algorithm well enough to do this myself. In fact, I'm not even certain if the assumptions it is based on still hold...
-Is it possible to adapt this algorithm to my needs?
-Or is there another linear algorithm I could use that is similarly efficient?
-Could anyone provide pseudocode or a detailed explanation?
Thanks.
Link to the Subset-Sum code I was investigating: Fast solution to Subset sum algorithm by Pisinger
(Apologies if this is poorly worded/formatted/etc. I'm still new to StackOverflow...)
Pisinger's algorithm gives you the largest sum less than or equal to the capacity of the knapsack. To solve your problem, use Pisinger to figure out what not to put in the subset. Formally, let the items be w_1, ..., w_n and the minimum be K. Give w_1, ..., w_n and w_1 + ... + w_n - K to Pisinger, then take every item that Pisinger does not.
这篇关于线性算法找到最小子集和超过阈值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
