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