Subset with smallest sum greater or equal to k

Question

I am trying to write a python algorithm to do the following. Given a set of positive integers S, find the subset with the smallest sum, greater or equal to k.

For example: S = [50, 103, 85, 21, 30] k = 140

subset = [85, 50, 21] (with sum = 146)

The numbers in the initial set are all integers, and k can be arbitrarily large. Usually there will be about 100 numbers in the set.

Of course there's the brute force solution of going through all possible subsets, but that runs in O(2^n) which is unfeasable. I have been told that this problem is NP-Complete, but that there should be a Dynamic Programing approach that allows it to run in pseudo-polynomial time, like the knapsack problem, but so far, attempting to use DP still leads me to solutions that are O(2^n).

Is there such a way to appy DP to this problem? If so, how? I find DP hard to understand so I might have missed something.

Any help is much appreciated.

A pseudo-polynomial time approach could consider all possible values [0.1, 0.2, ...14.6]. Now start with 0.1 and build your possible solutions up to 14.6. For building a solution for 14.6 you can use your results for (0.1, 14.5) and (0.2, 14.4) and so on. — SaiBot
Sort the numbers. Do DFS adding highest unused value and stopping when you exceed k, then backtrack to find next solution. Stop when the remaining numbers can't add to k. With only a 100-deep stack a recursive solution probably works ok. — stark

Photon Photon · Accepted Answer · 2019-05-08T16:44:44

Well seeing that numbers are not integers but reals, best I can think of is O(2^(n/2) log (2^(n/2)).

It might look worse at first glance but notice that 2^(n/2) == sqrt(2^n)

So to achieve such complexity we will use technique known as meet in the middle:

Split set into 2 parts of sizes n/2 and n-n/2
Use brute force to generate all subsets (including empty one) and store them in arrays, let's call them A and B
Let's sort array B
Now for each element a in A, if B[-1] + a >=k we can use binary search to find smallest element b in B that satisfies a + b >= k
out of all such a + b pairs we found choose the smallest

OP changed question a little now its integers so here goes dynamic solution:

well not much to say, classical knapsack.

for each i in [1,n] we have 2 options for set item i: 1. Include in subset, state changes from (i, w) to (i+1, w + S[i]) 2. Skip it, state changes from (i, w) to (i+1, w)

Every time we reach some w that`s >= k, we update answer

Pseudo-code:

visited = Set() //some set/hashtable object to store visited states
S = [...]//set of integers from input
int ats = -1;

 void solve(int i, int w) //theres atmost n*k different states so complexity is O(n*k)
{
    if(w >= k)
    {
        if(ats==-1)ats=w;
        else ats=min(ats,w);
        return;
    }
    if(i>n)return;

    if(visited.count(i,w))return; //we already visited this state, can skip
    visited.insert(i,w)=1;

    solve(i+1, w + S[i]); //take item
    solve(i+1, w); //skip item
}

solve(1,0);
print(ats);

Subset with smallest sum greater or equal to k

1 Answers