Hi all,
I need a little help regarding simple optimization:
There are a given number of pairs of positive numbers for e.g. [latex](a_1, b_1), (a_2, b_2)... (a_N, b_N)[/latex]. The objective is to choose a subset [latex]S[/latex] of some pairs:
[latex]\max \sum_{i \in S} a_i[/latex]
s.t [latex]\sum_{i \in S} b_i\le B[/latex]
In other words, this problem can be thought as follows: You have some bank balance [latex]B[/latex] and there are number of different products in the market of price lets say [latex]b_i[/latex] that give some utility [latex]a_i[/latex]. Objective is to maximize utility (choose some number of products) subject to bank balance. What are such kind of problems called? Also, you can also assume that whenever [latex]b_1>b_2[/latex], then [latex]a_1>a_2[/latex] that is whenever something is expensive, it also gives better utility. I am not sure if this could be important.
Also if possible, can someone suggest how could this be solved (a fast method rather than exhaustive search)? (Taking the maximum [latex]a_i[/latex]'s until the budget is satisfied is not optimal in general for e.g. large number of small cheap products can give better overall utility than fewer high utility expensive products).
Thanks