线性算法找到最小的子集之和超过阈值 [英] Linear algorithm to find minimum subset sum over a threshold
问题描述
我有N个正整数的集合，每个北临一个（相对较小）不变C.我想找到这些数字与最小的总和大于（或等于）一个K值的一个子集。
涉及的数字不是非常大（小于100），但我需要良好的性能，即使在最坏的情况下。我想也许我可以适应Pisinger的动态规划算法的任务;它运行在O（NC）的时候，我碰巧遇到有界，正数的要求。
：这些数字是没有排序，可能有重复
不过，我不明白的算法足够好，这样做我自己。事实上，我甚至不能肯定，如果假设它仍然是基于举行...
-is有可能这个算法适应我的需要？
- 或者是有另一种线性算法，我可以用这同样是有效的？
-Could任何人提供假code或详细的解释？
感谢。
链接到子集琛code我正在调查： <一href="http://stackoverflow.com/questions/9962568/fast-solution-to-subset-sum-algorithm-by-pisinger">Fast解决方案通过Pisinger 以子集和算法
（道歉，如果这是措辞不当/格式化/等。我还是新的计算器...）
Pisinger的算法，给你最大的总和小于或等于背包的容量。要解决问题，使用Pisinger弄清楚什么的没有的投入子集。从形式上看，我们的项目是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屋！
