Algorithm to select a set of numbers to reach a minimum total

Question

Given A set of numbers n[1], n[2], n[3], .... n[x] And a number M

I would like to find the best combination of

n[a] + n[b] + n[c] + ... + n[?] >= M

The combination should reach the minimum required to reach or go beyond M with no other combination giving a better result.

Will be doing this in PHP so usage of PHP libraries is ok. If not, just a general algorithm will do. Thanks!

Answer 1

what do you mean by "best"? Least number of n[i]? smallest standard deviation in the n[i]? Impossible to say unless you define "best"?

Answer 2

I think that a greedy algorithm approach will work. How many numbers do you expect to have in the set? If it is reasonably low you could try backtrack, but I would not recommend it for large sets.

Answer 3

I think this is NP-complete (it's not possible to find a fast way of doing it in general). The way you've phrased the question makes me think of solving successive Subset sum problems with a target integer that steadily increases from M.

In your example, there is no known method of determining whether M can be reached. Only a brute-force solution would tell you that it's not possible, and only then could you check M+1.

However, you may like to look at the DP solution, as this will at least give you an idea of how to solve the problem (albeit slowly). There is also an approximate solution which will be correct if your numbers are small. Use this. Finally, it's worth pointing out that the size of the problem is measured in the number of bits, not the size (or sum) of the set.

As mentioned above, this is related to the Knapsack problem.

Answer 4

This kind of problems is called binary linear programming (a special case of integer linear programming). It is famously NP-hard – i.e. not efficient to solve in general.

However, there exist good solvers, both commercial and free use, e.g. the Open Source solver lpsolve which you can call from your program.

/EDIT: Old answer was bunk. I confused the factors.

Answer 5

A Greedy solution would work A pseudo:

algo(input_set , target_sum, output_set )
   if input_set is NULL
       error "target_sum can never be reached with all input_set"
       return
   the_max = maximum(input_set)
   remove the_max from input_set
   if the_max > target_sum
       algo(input_set, target_sum, ouptput_set )
       return
   add the_max to output_set
   algo(input_set, target_sum - the_max, output_set )

call with output_set = NULL. sort intput_set for efficiency.

Answer 6

This problem is almost exactly the subset sum problem, which is related to the Knapsack problem but different, and is NP complete. However, there is a linear solution if all the numbers are smaller than some constant, and a Polynomial time approximation. See the wikipedia page referenced above.

Answer 7

pseudocode:

list<set> results;
int m;
list<int> a;

// ...    

a.sort();

for each i in [0..a.size]
    f(i, empty_set);    

// ...

void f(int ind, set current_set)
{
    current_set.add(a[ind]);

    if (current_set.sum > m)
    {
        results.add(current_set);
    }
    else
    {
        for (int i=ind + 1; i<a.size; ++i)
        {
            f(i, current_set);  // pass set by value

            // if previous call reached solution, no need to continue
            if (a[ind] + current_set.sum) > m
                break;
        }
    }
}

// choose whatever "best" result you need from results, the one
// with the lowest sum or lowest number of elements

Answer 8

This looks like a classic Dynamic Programming problem (also indicated by other answers mentioning its similarity to 0-1 Knapsack and Subset Sum problems). The whole thing boils down to to one simple choice: for each element in the list, do we use it in our sum or not. We can write up a simple recursive function to compute the answer:

f(index,target_sum)=
     0     if target_sum<=0 (i.e. we don't need to add anymore)
     infinity   if target_sum>0 and index is past the length of n (i.e. we have run out of numbers to add)
     min( f(index+1,target_sum), f(index+1,target_sum-n[index])+n[index] )    otherwise (i.e. we explore two choices -  1. take the current number 2. skip over the current number and take their minimum)

Since this function has overlapping subproblems (it explores the same sub-problems over and over again) , it is a good idea to memoize the function with a cache to hold values that were already computed before.

Here's the code in Python:

#! /usr/bin/env python

INF=10**9 # a large enough number of your choice

def min_sum(numbers,index,M, cache):
    if M<=0: # we have reached or gone past our target, no need to add any more
        return 0
    elif len(numbers)==index: # we have run out of numbers, solution not possible
        return INF
    elif (index,M) in cache: # have been here before, just return the value we found earlier
        return cache[(index,M)]
    else:
        answer=min(
            min_sum(numbers,index+1,M,cache), # skip over this value
            min_sum(numbers,index+1,M-numbers[index],cache)+numbers[index] # use this value
        )
        cache[(index,M)]=answer # store the answer so we can reuse it if needed 
        return answer 

if __name__=='__main__':
    data=[10,6,3,100]
    M=11

    print min_sum(data,0,M,{})

This solution only returns the minimum sum, not the actual elements used to make it. You can easily extend the idea to add that to your solution.