Optimisation of options under a budget constraint

Question

I don't really know where to begin with solving this problem. I think I'll probably have to use some code but I'm not even sure how to approach the code.

I have two categories and from category 1, I have to pick 5 options and from category 2, I have to pick 1 option. My total budget is 100.0 and each option has a price and an expected value shown below:

Category 1 (Expected Value/Price/EV per unit price):

1. 50.5/33.5/1.51
2. 37.5/24.8/1.51
3. 28.5/23.6/1.21
4. 24.5/18.4/1.33
5. 26.5/17.3/1.53
6. 17.5/13.1/1.28
7. 19/16.8/1.13
8. 16/16.2/0.99
9. 14.5/15.6/0.93
10. 6/14.4/0.42
11. 3/13.9/0.22
12. 3/10.1/0.30
13. 8/11.7/0.68
14. 3/8.8/0.34
15. 8/9.6/0.83
16. 7/6.2/1.13
17. 2/7.9/0.25
18. 2/6.5/0.31
19. 7/5.5/1.27
20. 2/5.8/0.34

Category 2 (Expected Value/Price):

1. 71/38.0/1.87
2. 59/25.9/2.28
3. 37/18.9/1.98
4. 20/18.1/1.10
5. 14/17.6/0.80
6. 11/15.4/0.71
7. 6/12.7/0.47
8. 5/8.9/0.56
9. 4/6.3/0.63
10. 4/6.1/0.66

Is there any strategy I should follow to optimise my expected value while sticking to the budget. There is no reason not to use my entire budget.

Would appreciate it if anyone had any ideas!

Answer 1

This is a variant of the 0-1 knapsack problem.

You can solve it via integer linear programming as follows. Let binary decision variable $x_i$ indicate whether option $i$ is selected. You want to maximize $\sum_i v_i x_i$ subject to linear constraints \begin{align} \sum_{i \in \text{category 1}} x_i &= 2 \\ \sum_{i \in \text{category 2}} x_i &= 1 \\ \sum_i p_i x_i &\le 100 \\ \end{align}

You can also solve it via dynamic programming.