I was trying to code a simple economics simulator where consumers try and maximize their utilities based on a lot of parameters and I think that maximizing utilities is NP-hard but I wanted to ask you guys to make sure I am right. I think you can show that it is equivalent to a knap-sake formation.
Here is the problem: There are n goods each of which has $v_i$ value and price $p_i$. For each item, $i$ the item has a complement/substitute value $c_{i,j}. \in [0,\inf)$ for each other item. $c_{i,j}= 1$ if the Agent has not bought item j. An agent has $m$ dollars to spend. The agent gets utility $u = c_{i,j} * v_i$
Finding a way to maximize utility with the constraint of spending less than or equal to m dollars. The added constraint of the complement/substitute makes it so buying the good with the greatest value doesn't work and other greedy algorithms seem like they won't work.
Please let me know your thoughts! Thanks