Given a set $A$ of $n$ positive integers $a_1, a_2,\ldots, a_n$ and another positive integer $M$, I'm going to find a subset of numbers of $A$ whose sum is closest to $M$. In other words, I'm trying to find a subset $A′$ of $A$ such that the absolute value $|M - \sum_{a∈A′}a|$ is minimized. I only need to return the sum of the elements of the solution subset $A′$ without reporting the actual subset $A′$.
For example, if we have $A$ as $\{1, 4, 7, 12\}$ and $M = 15$, then the solution subset is $A′ = \{4, 12\}$, and thus the algorithm only needs to return $4 + 12 = 16$ as the answer.
The dynamic programming algorithm for the problem should run in $O(nK)$ time in the worst case, where $K$ is the sum of all numbers of $A$.