Given an array of lengths, find closest combination to a total length

Question

I have two sets of variables, a static array of segment lengths and a dynamic final total length to be specified by the user.

For example, array lengths = [50,40,80,30,108,25], total = 150.

How would I go about calculating the optimal combination of the lengths array values to get as close as possible to the specified total number? Using only addition. As we are using segments with a specified length to get as close as possible to a target length.

Not all array values have to be used. Each array element can be used an unlimited amount of times, but we want to get to the final result using the least amount of math as possible (i.e. do not want to do 25+25, instead of just using the 50)

Answer 1

This problem is NP-hard because an NP-complete variation of the subset sum problem can be reduced to it. The variation is that elements of the set can be used more than once. It can also be viewed as a variation of the change-making problem; see this question on cstheory.SE for details.

If there is a combination with a sum exactly equalling the total, then that is the optimal solution so your algorithm would find it. Inversely, if there is no such combination, your algorithm would find a solution with a different sum; the fact that that different combination is optimal would prove that no subset exactly equals the sum.

So, since your problem is NP-hard, that means there is no known algorithm which gives exact answers and also scales efficiently to large inputs. If you need an algorithm which finds truly optimal solutions, then you won't do much better than some kind of backtracking search. Otherwise, if "good enough" is good enough, it is worth reading about heuristic algorithms for the subset sum problem, which can likely be adapted to your problem in a straightforward way.