Given a set of numbers (negative or positive), and a maximum weight w, find a subset that is maximal whose sum is less than w

The aim of this problem is to find a subset (need not be consecutive) of a given set such that the sum is maximal and less than some given number $w$. (Note, we are trying to find a subset that is less than or equal to $w$ and not closest to $w$).

For example, given a set $\{1, 3, 5, 9, 10\}$ and maximum weight 17, the maximal subset is $\{3, 5, 9\}$ since its sum is exactly 17.

Another example: given a set $\{1, 3, 4, 9\}$ and maximum weight 15, the maximal subset is $\{1, 4, 9\}$ since its sum is 14, and there are no other subsets whose sum is 15.

Example with both positive and negative numbers: given a set $\{-3, 2, 4\}$ and maximum weight 3, the subset is the set itself since -3 + 2 + 4 = 3.

I know how to solve it with only positive numbers, but I am struggling to find an algorithm to solve this problem for the general case with both positive and negative numbers. Obviously, my goal is not to use the brute force approach and check every possible subset since the complexity would be $O(n2^n)$.

I stumbled upon an idea on another post that suggested adding a sufficiently large number to every elements in the set and subsequently changing the maximum weight. That is given a set $R = \{ a_1, a_2, ... , a_n \}$, we add some number $X$ (we can pick some number greater than equal to the absolute value of the smallest negative number) to get a set that looks like $\{ a_1 + X, a_2 + X, ... , a_n + X \}$ and change the maximum weight to $nX + w$ where $w$ was the original weight. Now, we have reduced the problem to only non-negative numbers. However, I could not see a way to actually find the subset that was closest to the original weight, but only whether any elements add up exactly the original weight (ie, there is no way to actually find the subset, but only to determine that some subset exists).

Is there any other clever trick like this one to solve the problem for both positive and negative numbers? Any help would be thoroughly appreciated.

• Since you see "need not be consecutive", what on earth would a "consecutive subset" be? – gnasher729 Jul 28 '16 at 13:05

Given a set of numbers $\{a_1,\dots,a_n\}$, let $best(i, w)$ be the best solution using only a subset of the elements $a_i,\dots,a_n$ with a maximum value $w$, then $$best(i,w) = max(a_i + best(i+1,w-a_i), best(i+1,w))$$ With boundaries conditions $best(n + 1,w) = -\infty$ for any $w < 0$, and $best(n + 1,w) = 0$ otherwise.