# complexity of a variant of the subset sum problem

We have a set of positive integers $$N=\{a_1,...,a_n\}$$, we want to select a subset $$N'$$ of $$N$$ with maximum total sum of integers such that this sum should not exceed a given integer $$B$$.

What is the complexity of this problem.

It is NP-hard. Given an instance of your problem, the sum of the integers in the optimal subset $$N'$$ is at least $$B$$ (which implies that it must actually be exactly $$B$$) if and only if the corresponding subset sum instance has answer "yes".
• but to prove the reverse, if we suppose that I have a solution to my problem, it means I have a subset $N'$ of N of sum <=$B$ (not necessarily $B$), how can I found a solution to the subset sum problem? – Farah Mind Oct 9 at 21:22
• If $N'$ is an optimal solution to your problem and the elements of $N'$ sum to $B$, then $N'$ is also solution to the subset sum problem. If the elements sum to less than $B$, then the subset sum problem admits no solution. – Steven Oct 9 at 21:24
• Indeed that implication is false. Notice however that at no point I claimed such a thing. I said that if your problem has a solution with measure at least $B$, then subset sum has a solution, and vice-versa. I.e., if you are able to solve your problem (meaning that you can find an optimal solution) then you can also solve subset sum: you can decide whether there is a subset of numbers that sums to $B$ and, if that is the case, you can also exhibit one such subset. Also notice that, as long as $B\ge0$, your problem always has a solution (since $N'=\emptyset$ is a feasible solution). – Steven Oct 9 at 21:53