1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Nov 15 '15 at 10:03
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Nov 15 '15 at 10:05
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.