views:

2975

answers:

9

I have a decimal number (let's call it goal) and an array of other decimal numbers (let's call the array elements) and I need to find all the combinations of numbers from elements which sum to goal.

I have a preference for a solution in C# (.Net 2.0) but may the best algorithm win irrespective.

Your method signature might look something like:

public decimal[][] Solve(decimal goal, decimal[] elements)
+8  A: 

I do believe you picked a rather hard problem

Tom Ritter
+3  A: 

I think you've got a bin packing problem on your hands (which is NP-hard), so I think the only solution is going to be to try every possible combination until you find one that works.

Edit: As pointed out in a comment, you won't always have to try every combination for every set of numbers you come across. However, any method you come up with has worst-case-scenario sets of numbers where you will have to try every combination -- or at least a subset of combinations that grows exponentially with the size of the set.

Otherwise, it wouldn't be NP-hard.

Rob Dickerson
Not every... Once the sum of a certain combination exceeds the target number, you can stop calculating that branch and move on to the next.
Haoest
+1  A: 

You have described a knapsack problem, the only true solution is brute force. There are some approximation solutions which are faster, but they might not fit your needs.

ARKBAN
+2  A: 

The subset-sum problem, and the slightly more general knapsack problem, are solved with dynamic programming: brute-force enumeration of all combinations is not required. Consult Wikipedia or your favourite algorithms reference.

Although the problems are NP-complete, they are very "easy" NP-complete. The algorithmic complexity in the number of elements is low.

Steve Jessop
+3  A: 

Interesting answers. Thank you for the pointers to wikipedia - whilst interesting - they don't actually solve the problem as stated as I was looking for exact matches - more of an accounting / book blancing problem than a traditional bin-packing / knapsack problem.

I have been following the development of stack overflow with interest and wondered how useful it would be. This problem came up at work and I wondered whether stack overflow could provide a ready made answer (or a better answer) quicker than I could write it myself. Thanks also for the comments suggesting this be tagged homework - I guess that is reasonably accurate in light of the above.

For those who are interested, here is my solution which uses recursion (naturally) I also changed my mind about the method signature and went for List> rather than decimal[][] as the return type:

public class Solver {

    private List<List<decimal>> mResults;

    public List<List<decimal>> Solve(decimal goal, decimal[] elements) {

        mResults = new List<List<decimal>>();
        RecursiveSolve(goal, 0.0m, 
            new List<decimal>(), new List<decimal>(elements), 0);
        return mResults; 
    }

    private void RecursiveSolve(decimal goal, decimal currentSum, 
        List<decimal> included, List<decimal> notIncluded, int startIndex) {

        for (int index = startIndex; index < notIncluded.Count; index++) {

            decimal nextValue = notIncluded[index];
            if (currentSum + nextValue == goal) {
                List<decimal> newResult = new List<decimal>(included);
                newResult.Add(nextValue);
                mResults.Add(newResult);
            }
            else if (currentSum + nextValue < goal) {
                List<decimal> nextIncluded = new List<decimal>(included);
                nextIncluded.Add(nextValue);
                List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
                nextNotIncluded.Remove(nextValue);
                RecursiveSolve(goal, currentSum + nextValue,
                    nextIncluded, nextNotIncluded, startIndex++);
            }
        }
    }
}

If you want an app to test this works, try this console app code:

class Program {
    static void Main(string[] args) {

        string input;
        decimal goal;
        decimal element;

        do {
            Console.WriteLine("Please enter the goal:");
            input = Console.ReadLine();
        }
        while (!decimal.TryParse(input, out goal));

        Console.WriteLine("Please enter the elements (separated by spaces)");
        input = Console.ReadLine();
        string[] elementsText = input.Split(' ');
        List<decimal> elementsList = new List<decimal>();
        foreach (string elementText in elementsText) {
            if (decimal.TryParse(elementText, out element)) {
                elementsList.Add(element);
            }
        }

        Solver solver = new Solver();
        List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());
        foreach(List<decimal> result in results) {
            foreach (decimal value in result) {
                Console.Write("{0}\t", value);
            }
            Console.WriteLine();
        }


        Console.ReadLine();
    }
}

I hope this helps someone else get their answer more quickly (whether for homework or otherwise).

Cheers...

Sam Meldrum
A recursive solution would be 1/3 of the length and 3 times more elegant.
Haoest
It is a recursive solution. I'd be interested to see your solution that's 1/3 the length. Maybe you should actually examin the solution before commenting?
Sam Meldrum
Exact matches are the closest match. If the closest match isn't the exact match, then there is no exact match.
wnoise
"they don't actually solve the problem as stated"? The wikipedia links are completely relevant. Horowitz and Sahni is the approach to take.
Will
I know this was ~2 years ago, but is there any chance you might write your first piece of code in pseudo-code? I currently only know Python and I really can't read C#. I've tried my best at rewriting in Python but I don't understand some of the syntax and my code's giving me an empty list :P
vlad003
+2  A: 

Hey Sam,

While not solving the problem of brute force (as others already mentioned) you might want to sort your numbers first, and then go over the possible ones left (since once you passed Sum value, you can't add any number larger than Goal - Sum).

This will change the way you implement your algorithm (in order to sort only once and then skip marked elements), but on the average would improve performance.

Adi
Adi, Thanks for the suggestion. A good improvement for the general case, My solution actually works better for the problem I have but I didn't give you enough information to know that. The numbers are in date order and are more likely to sum in that order as the dates are important to the totals.
Sam Meldrum
A: 

public class Logic1 { static int val = 121; public static void main(String[] args) {

        f(new int[] {1,4,5,17,16,100,100}, 0, 0, "{"); 
} 

static void f(int[] numbers, int index, int sum, String output) 
{ 
        System.out.println(output + " } = " + sum); 
        //System.out.println("Index value1 is "+index);
        check (sum);
        if (index == numbers.length) 
        { 
                System.out.println(output + " } = " + sum); 
                return; 
        } 

        // include numbers[index] 
        f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]); 
       check (sum);
        //System.out.println("Index value2 is "+index);    
        // exclude numbers[index] 
        f(numbers, index + 1, sum, output); 
                check (sum);

} 
static void check (int sum1)
{
    if (sum1 == val)
            System.exit(0);


}

}

guest
A: 

i have a similar question, but i'm not sure if it's NP hard: suppose the array of elements is 1..goal , and i have to find the number of combinations of sums. for example: if the goal is 5 , the elements allowed to be used are [1,2,3,4,5] , so the combinations are: [5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1] so that answer would be 7 , since that's the number of combinations that exist .

bugmenot5214
I would ask this on math overflow. I'm sure there is an equation for this. I just don't know it.
Lumpy
A: 

If i had S (for example, [15,12,19,6,8,25]) then how can i find the numbers in S
whose sum equals to a given number like maybe 40

Mallepally
This should be a separate question.
Lumpy