CODEWITHSUNDEEP
algorithm
Migol
Migol

Reputation: 8447

Create a sum of 1000, 2000, etc. from set of numers

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?

Upvotes: 1

Views: 252

Answers (3)

Jerry Coffin
Jerry Coffin

Reputation: 490408

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.

Upvotes: 5

Mongoose
Mongoose

Reputation: 4645

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.

Upvotes: 2

Håvard S
Håvard S

Reputation: 23886

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.

Upvotes: 1

Related Questions