I have been given a problem phrased in the following terms:
John's mother asked him to go to the department store to buy Christmas decorations. Assume that each decoration item has price $p_i$ and utility $u_i$. John has a total budget of $B$ and aims to purchase items such that $\sum u$ is maximized. Given the set $\lbrace (p_i,u_i)\rbrace$ and $B$, how should John shop?
I tried thinking about this problem as each merchandise being a vector in Q1 of $\mathbb{R}^2$, and the task is to find a subset of vectors such that when connected they do not go beyond $x=B$, ($\sum x_{chosen}\leq B)$, yet maximizes the ultimate height ($y=\sum u_{chosen}$)
Of course there is the brute force method, but it has factorial time complexity so it's not a good option.
I couldn't get meaningfully far into this problem and would love to receive some guidance.