Say I have a list {1,3,7,2,11,8,2} and I want to take x elements from the list and get the value 15.5.

Is there an algorithm that would give me x elements in a list that, when added together, get nearest to this given value?

There is no preferred amount of elements, I just want to get as close to the given as possible.

I plan on implementing this algorithm in Swift (Object Oriented) if that makes any difference.

  • 3
    This is the subset sum problem which is well studied. – user40980 Jan 5 '15 at 5:57
  • You say list and your list is obviously not sorted. Intentionally? – Wolf Jan 5 '15 at 12:41

For a small dataset and a fixed value for the total and the number of elements, I would just do a modified brute force that was based on enumerating all the x number elements and discarding each less optimal solution as you go. I wouldn't bother to over-optimize it.

If you're talking about a changing data set and repeated variances of x and quantity, then I would start looking for more advanced options.

  • I am thinking about using an iTunes library as the dataset and a user controlled x. So optimizing the algorithm would definitely be the ideal solution. – Peter Kaminski Jan 5 '15 at 5:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.