2

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.

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

1 Answer 1

0

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.

1
  • 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. Commented Jan 5, 2015 at 5:55

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