# How do I model this expression maximization problem as a Knapsack problem?

Given two arrays of the same length $n$:

$A = \{a_1,a_2,\dots,a_n\}$,

$B = \{b_1,b_2,\dots,b_n\}$,

I have to maximize the following expression:

$$\frac{a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k}}{b_{i_1} + b_{i_2} + b_{i_3}+ \dots + b_{i_k}}$$

Where $k \lt n$.

Given the constraints:

Firstly, when you select a particular $a_i$ you have select it's corresponding $b_i$, and vice versa.

Secondly, you have to select exactly $k$ elements from the arrays. Where $k \lt n$.

Assumptions:

The assumption is that $A$ and $B$ both contain natural numbers only.

What I have tried:

I have tried sorting the arrays using the ratio $\frac{a_n}{b_n}$ in the non-decreasing order, but this gives an incorrect result since it's trying to optimize $\frac{a_1}{b_1} + \frac{a_2}{b_2} + \dots \frac{a_k}{b_k}$. That is different from my desired objective function.

I have also thought of treating the denominator as a knapsack but this does not make sense because there are no weights involved.

Any suggestion on what I can do to model this problem as a knapsack optimization problem?

## 1 Answer

One approach (not based on the knapsack problem): suppose you are given a threshold $\tau$ and want to check whether you can find a subset such that

$$\frac{a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k}}{b_{i_1} + b_{i_2} + b_{i_3}+ \dots + b_{i_k}} \ge \tau.$$

Could you solve that problem? If you could, you could use binary search on $\tau$.

Note that the above condition is equivalent to

$$a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k} \ge \tau \cdot (b_{i_1} + b_{i_2} + b_{i_3}+ \dots + b_{i_k}),$$

or equivalently,

$$a_{i_1} - \tau b_{i_1} + a_{i_2} - \tau b_{i_2} + a_{i_3} - \tau b_{i_3} + \dots + a_{i_k} - \tau b_{i_k} \ge 0.$$

And that enables us to find a simple way to check for the existence of that subset.

See if that gives you any ideas.

• How would I know what are my particular selections of $k$ by just selecting $\tau$ ? Take for instance a select a value of $\tau$ I still need to know what are the exact elements that comprise my set of $k$ elements. How does binary search help me for that? If the exact $k$ elements were known then maybe, but without it I don't get it how to do it. – ng.newbie Aug 22 '18 at 15:34
• @ng.newbie, Binary search doesn't help you find those elements; you'll have to figure out how to solve that problem. This is your exercise, so I'm leaving something for you to do. Based on your question, I believe that if you spend some time on it you will be capable of finding a solution for that part. So spend some time thinking about that one and see what you can come up with. – D.W. Aug 22 '18 at 18:56
• Okay so you think is it possible to maximize a fraction/ratio by the use of DP in any way? DP can maximize the profit, but I know that is true when the profit function is just where you add the value, ie. an addition function. But what happens when the profit function is changed to something more complex? Like a math expression with multiplication and division. Does Knapsack or any other DP work there? – ng.newbie Aug 24 '18 at 7:16
• @ng.newbie, sorry, I can't understand any of that comment. At this point I'm going to leave it to you to solve your exercise -- I've given you a sketch of an approach that might lead you to a solution, but I'm not going to provide a complete solution here. (And nowhere does my answer say anything about dynamic programming.) I think that's probably all I have to say on the subject -- I'm going to leave it to you to take it the rest of the way there. – D.W. Aug 24 '18 at 7:54
• What I mean was the normal knapsack value function is $max(\sum {v_i})$, what if instead of $v_i$ you get a function that is something like in the question. Will knapsack work in that case? Provided you are not restricted on the items that you can pick. The normal profit function is just where you add the value and check the maximum, but what if it is a fraction/ratio? I hope I could explain my doubt. – ng.newbie Aug 27 '18 at 7:47