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

Question

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.

Answer 1

This problem can be solved by a rather simple dynamic programming:

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.

Note that this problem is NP-hard because it solves the partition problem, in particular the running complexity of the above program depends on the given numbers, and can be exponential in the size of the input in the worse case.

Answer 2

As Gilad pointed out the problem is NP-hard.

You can note that it is a special case of the Knapsack Problem where the value and weight of the items are equal. It might therefore be interesting for you to explore a bit the solution methods for this generalization of your problem...