查找超过阈值的最小子集和的线性算法
我有N个正整数的集合，每个正整数都由一个（相对较小的）常数C界定。我想找到这些数字的子集，其最小总和大于（或等于）值K。
涉及的数字并不是很大（<100），但是即使在最坏的情况下，我也需要良好的性能。我以为也许我可以使Pisinger的动态编程算法适应这项任务。它以O（NC）时间运行，而我恰好满足有界正数的要求。
[编辑]：数字未排序，可能重复。
但是，我对算法的理解不足以自己完成。实际上，我什至不确定它所基于的假设是否仍然成立…
-是否可以根据我的需要调整此算法？
-还是我可以使用另一种效率类似的线性算法？
-谁能提供伪代码或详细说明？
谢谢。
回答：
Pisinger的算法为您提供的最大总和小于或等于背包的容量。要解决您的问题，请使用Pisinger找出 _不包含_在子集中的内容。正式地，让项目为w_1，…，w_n，最小值为K。将w_1，…，w_n和w_1 + … + w_n-K交给Pisinger，然后将Pisinger不需要的所有项目都拿走。
以上是 查找超过阈值的最小子集和的线性算法 的全部内容， 来源链接： utcz.com/qa/402844.html
