2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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)

$\endgroup$

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