Linear algorithm to find minimum subset sum over a threshold

3
votes

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

2
c++algorithmsubset-sum
isn't this a variant of Knapsack Problem? – phoeagon
Yes. Specifically, a variant of Subset-Sum (itself a special case of Knapsack). – Athena
For future reference, try to avoid using the term "set" if there are duplicates. "collection" would be a better term. – Nathan Henkel

2 Answers

4
votes

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.

0
votes

Well one solution is to:

T = {0}

for x in V
   for t in T
       T.insert(x+t)

for i in K to max(T)
   if (T.contains(i))
       return i

fail

This gives you the size of the subset, but you can adapt to output the members.

The maximum size of T is O(N) (because of C bound), so the running time is O(N^2) and the space is O(N). You can use a bit array of length NC as the backing store of T.