Algorithm for selecting specific number of elements from a set to reach some value

Given set of elements n[1], n[2], n[3], .... n[x] and a number V. (Elements have their own values)

I would like to find all combinations of elements which satisfies the following conditions:

1) Each combination contains specific number of elements (e.g: exactly 5 elements)

Combination#1: n[1], n[2], n[21], n[22], n[24]

Combination#2: n[1], n[2], n[12], n[15], n[33]

......

2) Sum of elements values in combination must开发者_如何学运维 be smaller than given number V (e.g V = 100)

Combination#1: n[1] + n[2] + n[21] + n[22] + n[24] < 100

Combination#2: n[1] + n[2] + n[12] + n[15] + n[33] < 100

......

I am trying to write a c# program which computes these elements. But language is not important, any algorithm satisfies these conditions is acceptable!

Thanks

Since you will probably have to use brute force anyway, you can solve your problem with the following approach:

First of all, sort your input set S.

Then remove all elements from S which are greater than V - 4*|min| (where |min| is the absolute value of the smallest element), because they won't appear in any of your solutions anyway. Depending on your exact problem specification, this optimization may be improved further.

Now you generate all sums of length C of elements in S, starting with the smallest possible numbers (remember that S is sorted).

If the result is smaller than V, add it to your solution set and increase the last summand.

Otherwise, set the previously increased summand and all summands after that one to their smallest possible values and increase the summand just before that.

You can stop if all summands have reached their highest possible values. You may be able to stop long before that, which is left as an exercise to the reader due to my sloppy English.

Im not so sure but maybe you can adapt this idea to have the condition that all combinations must have a certain amount of elements.

http://en.wikipedia.org/wiki/Knapsack_problem

However, it is said that the knapsack problem has a complexity of NP-complete to be solved exactly... That's bad news. So what people suggest to do, is using a backtracking algorithm.

I'm sure you will find a lot of codes in google about backtracking for the knapsack problem.

I hope this helps