2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Farah Mind Oct 9 at 21:22
  • $\begingroup$ 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. $\endgroup$ – Steven Oct 9 at 21:24
  • $\begingroup$ then the implication "my problem has a solution imply the subset sum problem has a solution" is not true $\endgroup$ – Farah Mind Oct 9 at 21:28
  • $\begingroup$ 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). $\endgroup$ – Steven Oct 9 at 21:53
  • $\begingroup$ I understand now what do you mean, but what makes me confused is the fact that when we try to prove the complexity of a maximization problem, we consider its decision problem in which we have the value of the objective function >= a given value. But in this case we have the value of the objective function <=B, how can we define the decision problem associated $\endgroup$ – Farah Mind Oct 9 at 22:17

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.