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

<p>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)</p>

CC BY-SA 4.0
2019-07-22T21:02:37.977Z
2019-07-22T21:02:37.977Z
Avi Tal
<p>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...</p>

<p>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.</p>

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

<optimization>
Sum From A List Of Numbers (Algorithm)
username
# Sum From A List Of Numbers (Algorithm)

(Asked by: username_0 on 2019-07-22)

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?

**Tags:** optimization

---

## 1 answers

### Answer by username_1 on 2019-07-22. Score: 4

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)


---

