0

Possible Duplicate:
Subset Sum algorithm

I have a very easy problem which I can't figure out. I'm given an array of numbers and a value I need to get as close as possible to by making combinations of the sets. This algorithm has to be recursively. The result can't exceed the given number.

For example, given an array of {6, 9, 4, 2, 7} and I need to get as close as possible to 14. Then the result is 13 (by choosing the elements 9 and 4).

This is what I have so far:

A recursive function with 2 parameters: an index that gives information about the element you're about to add (or not) and the sum so far. For every element I make a binary decision: add it to the sumSoFar or not. I'm a bit confused about the base cases since the result can't exceed the number I have to get as close as possible to.

Could anyone help me with this?

Thanks in advance!

4

1 回答 1

1

Try sth like this:

bestsum = 0;
recurisve(index, sum){
    if index > max_index{
        if sum is better than bestsum{
            bestsum = sum
        }
    }
    recursive(index + 1, sum + element[index]);
    recursive(index + 1, sum);
}

if sum is better than bestsum should check all condition to determine if, having two results: sum and bestsum, bestsum is better result than sum.

于 2012-12-19T10:45:37.950 回答