Use dynamic programming to find a subset of numbers whose sum is closest to given number M

Question

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$.

• David Richerby: Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered.
• David Richerby: Also, your post contains some kind of unicode character that isn't available in the standard fonts on Windows 7: the "􀀀" immediately after "such that the absolute value |M - ". You can use $\LaTeX$ to typeset mathematics and we have a brief help page on how to do that.

Answer 1

Hint: Use the classical dynamic programming algorithm to find all sums of subsets, and from that information deduce the sum closest to $M$.

You can actually improve this algorithm in two ways. First, you can improve the running time to $O(n\min(K,M)),ドル using the fact that the optimal sum is at most 2ドルM$ (why?). Second, you can also find the optimal set $A'$ itself within the same time bound: just use the very same technique used to accomplish that for the usual SUBSET-SUM.