Ok, so here's the problem:
I need to find any number of intem groups from 50-100 item set that add up to 1000, 2000, ..., 10000.
Input: list of integers
Integer can be on one list only.
Any ideas on algorithm?
+5
A:
Googling for "Knapsack problem" should get you quite a few hits (though they're not likely to be very encouraging -- this is quite a well known NP-complete problem).
Edit: if you want to get technical, what you're describing seems to really be the subset sum problem -- which is a special case of the knapsack problem. Of course, that's assuming I'm understanding your description correctly, which I'll admit may be open to some question.
You might find Algorithm 3.94 in The Handbook of Applied Cryptography helpful.
Jerry Coffin
2009-12-19 00:11:14
It's not really this problem - in my case this is not optimalization - no need to get maximum number of results.
Migol
2009-12-19 00:15:44
Getting *a* result is just a special-case of getting *the best* result. You're still in NP-complete land, unfortunately.
Lasse V. Karlsen
2009-12-19 00:27:51
That's the answer, still O(n2^(n/2)) is sad but the best I can get.
Migol
2009-12-19 00:36:41
+1
A:
This is the knapsack problem. Are there any constraints on the integers you can choose from? Are they divisible? Are they all less than some given value? There may be ways to solve the problem in polynomial time given such constraints - Google will provide you with answers.
Håvard S
2009-12-19 00:14:37
Knapsack problem has two parameters - weight and value. I have only weight. Constarints are that they are in range 1 - 10000, nothing more.
Migol
2009-12-19 00:17:34
All integers can have a value of 1 in context of the algorithm, they can have value equal to their weight, or some other variant - it's just a matter of transforming your problem to fit the algorithm.
Håvard S
2009-12-19 00:22:59
+2
A:
I'm not 100% on what you are asking, but I've used backtracking searches for something like this before. This is a brute force algorithm that is the slowest possible solution, but it will work. The wiki article on Backtracking Search may help you. Basically, you can use a recursive algorithm to examine every possible combination.
Mongoose
2009-12-19 00:17:39