Help with combinatorial optimization

[moterpoker]

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

Edited September 18, 2011 by moterpoker

[moterpoker]

Nevermind. I found the answer. It is 0-1 Knapsack problem