1

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.

user202531
  • 41
  • Isn't this a classic linear programming problem? – Parcly Taxel Aug 09 '19 at 06:51
  • I am very new to optimization and am self-learning. Could you please point me to some relevant resources? Thank you! – user202531 Aug 09 '19 at 07:02
  • Parcly has pointed you in the right direction, look for Linear Programming. Try starting here: http://mathworld.wolfram.com/LinearProgramming.html. – badjohn Aug 09 '19 at 08:39
  • This is called the knapsack problem. The two main variants allow each item to be purchased either at most once or any nonnegative integer number of times. – RobPratt Aug 09 '19 at 12:33

0 Answers0