我有一个包含N个正整数的集合,每个数字都被一个(相对较小的)常量C限制。我想找到一个子集,使得它们的和最小且大于(或等于)一个值K。
这些数字并不是特别大(<100),但我需要在最坏情况下也能获得良好的性能。我认为我可以将Pisinger的动态规划算法适应到这个任务上;它的运行时间为O(NC),而我的要求是有界的正数。
[编辑]:这些数字没有排序,可能存在重复。
然而,我不太了解该算法,无法自己完成。事实上,我甚至不确定它所基于的假设是否仍然成立...
- 是否可能将此算法适应到我的需求中?
- 或者是否有另一个线性算法可以使用,效率类似?
- 任何人都可以提供伪代码或详细说明吗?
谢谢。
链接到我正在调查的Subset-Sum代码: Fast solution to Subset sum algorithm by Pisinger (如果这样表述/格式等不好,请谅解。我还是StackOverflow的新手...)
这些数字并不是特别大(<100),但我需要在最坏情况下也能获得良好的性能。我认为我可以将Pisinger的动态规划算法适应到这个任务上;它的运行时间为O(NC),而我的要求是有界的正数。
[编辑]:这些数字没有排序,可能存在重复。
然而,我不太了解该算法,无法自己完成。事实上,我甚至不确定它所基于的假设是否仍然成立...
- 是否可能将此算法适应到我的需求中?
- 或者是否有另一个线性算法可以使用,效率类似?
- 任何人都可以提供伪代码或详细说明吗?
谢谢。
链接到我正在调查的Subset-Sum代码: Fast solution to Subset sum algorithm by Pisinger (如果这样表述/格式等不好,请谅解。我还是StackOverflow的新手...)