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

Question

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?

Answer 1

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.