An answer to this question on Stack Overflow.

Question

I have a list of numbers, sorted descending, size of array is variable and any number can appear (typically less than 1000)

given an input number (x), I need to find the optimal combination of values in the list, that is larger than x by the smallest amount possible. I've been reading about the NP-optimization and sum subset type problems, but haven't found a solution yet. I've found some psuedocode for an approximate alogorithm, but i would like to find the exact optimal solution from the given list of numbers. thanks

Answer

This sounds very much like a knapsack problem. If it is, then finding an exact solution is not going to be easy.

Why is that? It is because the best solution may be comprised of potentially any subset for your numbers. There are 2^N subsets, so that is an extremely large space to search for solutions.

How large is it?

Items | Search Space          | How this feels
16    | 65,536                | I can do it!
32    | 4,294,967,296         | Better go get lunch
40    | 1,099,511,627,776     | If I only had a supercomputer
50    | 1,125,899,906,842,624 | I will watch as the last stars day

There are tricks and things which can reduce the search space, but you'll still hit epicly large problems for low item counts.

Given this, you should:

1. Choose only small problem sizes and use exhaustive search because it is easy to implement.
2. Learn about branch-and-bound and other search space reducing techniques
3. Approximate. Everyone does it.