moterpoker 0 Posted September 18, 2011 Share Posted September 18, 2011 (edited) 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 Link to post Share on other sites

moterpoker 0 Posted September 18, 2011 Author Share Posted September 18, 2011 Nevermind. I found the answer. It is 0-1 Knapsack problem Link to post Share on other sites

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now