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?