Subset whose sum is the smallest sum over a specific threshold

Question

Given a collection of positive integers, I want the subset of those integers whose sum is the smallest sum that exceeds a threshold.

Answer 1

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.

Answer 2

"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.