I came upon a problem and have been trying to find a method more efficient then brute force, but I came up with nothing; and I am not even sure how to approach it...

You have a list of numbers and a target number all of which are positive and can have decimals. You must add the numbers in the list to get as close as possible to the target value without overshooting. Each number in the list can be used any number of times including not at all. The solution is the closest number that uses the least total numbers. To be clear, the least total numbers only applies when there are two identically close solutions.

It isn't very hard to make a program that checks every possible combination, but is there a way to make it more efficient?


closed as off-topic by Emil Jeřábek, Gamow, Marzio De Biasi, Jan Johannsen, D.W. Jul 25 at 5:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Gamow, Marzio De Biasi, Jan Johannsen, D.W.
If this question can be reworded to fit the rules in the help center, please edit the question.


The problem is NP-Complete even for integer values. You can look up the "knapsack problem" to see why.

A pseudo-polynomial algorithm exists if you can map your N values to integers (if the number of decimal places are bounded by some constant)


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