  # moterpoker

Members

2

0 Neutral

• Rank
Lepton

## Profile Information

• Favorite Area of Science
Math
1. Nevermind. I found the answer. It is 0-1 Knapsack problem
2. Hi all, I need a little help regarding simple optimization: There are a given number of pairs of positive numbers for e.g. $(a_1, b_1), (a_2, b_2)... (a_N, b_N)$. The objective is to choose a subset $S$ of some pairs: $\max \sum_{i \in S} a_i$ s.t $\sum_{i \in S} b_i\le B$ In other words, this problem can be thought as follows: You have some bank balance $B$ and there are number of different products in the market of price lets say $b_i$ that give some utility $a_i$. 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 $b_1>b_2$, then $a_1>a_2$ 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 $a_i$'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
×