# NP-hardness of particular problem

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.

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.
• @Mohammad.Rostami If $P=NP$. Otherwise no, though special cases of the problem may have polynomial time algorithms as usual. Mar 16, 2023 at 16:59
• If $P\neq NP$ can you explain why my problem has no poly time solution? Mar 16, 2023 at 17:36
• @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. Mar 16, 2023 at 20:34