0
$\begingroup$

Suppose given two sets $\{a_1,a_2,\dots,a_n\},\{b_1,b_2,\dots,b_n\}$ of positive real numbers. We try to find a subset $I\subseteq\{1,2,3\dots,n\}$ such that: $\sum_{i\in I}b_i$ maximized and $\sum_{i\in I}a_i\leq 5$.

I think this problem is NP-hard but I can't reduce from famous problem like partition problem. Any help will be apricated.

$\endgroup$

1 Answer 1

2
$\begingroup$

This is the optimization form of the 0-1 Knapsack problem (Wikipedia).

In a 0-1 Knapsack problem, you have a set of items, each item having a weight and value. You have to select a set of items such that the sum of the values is maximized, but that the total weight of the items does not exceed the total capacity of the Knapsack. Here, the set $\{a_1, a_2, \ldots, a_n\}$ corresponds to the set of weights and the set $\{b_1, b_2, \ldots, b_n\}$ to the values, with the maximum weight being $5$.

The problem you posit is not a decision problem, and therefore is outside the classical definition of NP-hardness. However, it's easily converted into a decision problem asking whether a total value $V$ can be reached without exceeding the weight limit $W$. This version of the problem is NP-complete.

$\endgroup$
6
  • $\begingroup$ So, my problem can solved in poly time? $\endgroup$
    – ErroR
    Mar 16, 2023 at 14:25
  • $\begingroup$ @Mohammad.Rostami If $P=NP$. Otherwise no, though special cases of the problem may have polynomial time algorithms as usual. $\endgroup$
    – kviiri
    Mar 16, 2023 at 16:59
  • $\begingroup$ If $P\neq NP$ can you explain why my problem has no poly time solution? $\endgroup$
    – ErroR
    Mar 16, 2023 at 17:36
  • $\begingroup$ @Mohammad.Rostami Because the problem is NP-complete. If the problem (converted into a decision problem) has a polynomial solution, it implies $P=NP$. By contraposition, $P \neq NP$ implies no polynomial time solution to the problem. $\endgroup$
    – kviiri
    Mar 16, 2023 at 20:34
  • $\begingroup$ How you find out this is a NP-complete problem? Can you explain it? $\endgroup$
    – ErroR
    Mar 16, 2023 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.