Subset whose sum is the smallest sum over a specific threshold

Given a collection of positive integers, I want the subset of those integers whose sum is the smallest sum that exceeds a thre开发者_开发知识库shold.

---

Your problem is a variation on the Subset Sum Problem and is NP-complete.

To see why, let's assume that you have an algorithm that can solve your problem and it produces an answer with sum s. Then you have proven that there exists no subset of the integers that equals s - 1, i.e. you have a solution to the subset sum problem.

If performance is not an issue, you might as well just enumerate all possible sets. If performance is an issue, you could try looking on the Wikipedia page for ideas on how to optimize this sort of algorithm, such as by using dynamic programming. The algorithm on that page should in fact solve your problem almost as efficiently as the subset sum problem.

---

"smallest sum": there's a classical "max sum" problem, described well here: http://wordaligned.org/articles/the-maximum-subsequence-problem

This is just a tiny variation with a "exceeds a threshold" condition - just an extra IF statement in your loop.

---

I had the same problem! If all N integers are positive and are bounded by a constant C, then there is a solution, with time and space requirements of O(NC).

Pisinger discovered a linear-time dynamic programming algorithm to find the maximum value under a threshold, which is like the inverse of your problem. So, if you subtract your desired threshold from the total sum of the integers, you can use this new threshold with Pisinger's algorithm to find all the numbers NOT in the desired set.

Depending on the size of the integers in question, this may or may not be feasible.

Pisinger's paper: http://www.diku.dk/~pisinger/95-6.ps

Code: Fast solution to Subset sum algorithm by Pisinger