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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
10
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".
-
$\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$ Oct 9, 2019 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$– StevenOct 9, 2019 at 21:24
-
$\begingroup$ then the implication "my problem has a solution imply the subset sum problem has a solution" is not true $\endgroup$ Oct 9, 2019 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$– StevenOct 9, 2019 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$ Oct 9, 2019 at 22:17