Algorithm to pick values from array that sum closest to a target value?

Question

I have an array of nearly sorted values 28 elements long. I need to find the set of values that sums to a target value provided to the algorithm (or if exact sum cannot be found, the closest sum Below the target value).

I currently have a simple algorithm that does the job but it doesn't always find the best match. It works under ideal circumstances with a specific set of values, but I need a more robust and accurate solution that can handle a wider variety of data sets.

The algorithm must be written in C, not C++, and is meant for an embedded system so keep that in mind.

Here's my current algorithm for reference. It iterates starting at the highest value available. If the current value is less than the target sum, it adds the value to the output and subtracts it from the target sum. This repeats until the sum has been reached or it runs out of values. It asumes a nearly ascending sorted list.

//valuesOut will hold a bitmask of the values to be used (LSB representing array index 0, next bit index 1, etc)

void pickValues(long setTo, long* valuesOut)
{
    signed char i = 27;//last index in array
    long mask = 0x00000001;

    (*valuesOut) = 0x00000000;
    mask = mask<< i;//shift to ith bit
    while(i>=0 && setTo > 0)//while more values needed and available
    {
        if(VALUES_ARRAY[i] <= setTo)
        {
            (*valuesOut)|= mask;//set ith bit
            setTo = setTo - VALUES_ARRAY[i]._dword; //remove from remaining         }
        //decrement and iterate
        mask = mask >> 1;
        i--;
    }
}

A few more paramters:

• The array of values is likely to be Nearly Sorted ascending, but that cannot be enforced so assume that there is not sorting. In fact, there may also be duplicate values.

• It is quite possible that the array will hold a set of values that cannot create every sum within its range. If the exact sum cannot be found, the algorithm should return values that create the next Lowest Sum.

Answer 1

This problem is known as the subset sum problem, which is a special case of the Knapsack problem. Wikipedia is a good starting point for some algorithms.

Answer 2

If values are reasonably small, it's a simple dynamic programming (DP). Time complexity would be O(n * target) and memory requirements O(target). If that satisfies you, there're lots of DP tutorials on the web. For example, here the first discussed problem (with couns) is very much like yours (except they allow to use each number more than once):
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

update Yep, as other person noted, it's a simple case of knapsack problem.

Answer 3

As others have noted, this is same as the optimization version of subset sum problem, which is NP-Complete.

Since you mentioned that you are short in memory and can probably work with approximate solutions (based on your current solution), there are polynomial time approximation algorithms for solving the optimization version of subset sum.

For instance, given an e > 0, there is a polynomial time algorithm which uses O((n*logt)/e) space, (t is the target sum, n is the size of the array) which gives you a subset such that the sum z is no less than 1/(1+e) times the optimal.

i.e If the largest subset sum was y, then the algorithm finds a subset sum z such that

z <= y <= (1+e)z

and uses space O((n*logt)/e).

Such an algorithm can be found here: http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf

Hope this helps.