Problem Detail: 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$.
Asked By : Amir Hossein F
Answered By : Yuval Filmus
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(nmin(K,M))$, using the fact that the optimal sum is at most $2M$ (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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/49508 Ask a Question Download Related Notes/Documents
