Minimize Sum a_i / Sum b_i over subsets I have two positive finite sequences $a_i$ and $b_i$, with $0 \leqslant i \leqslant n$. The problem is to find the subset $I$ of $\{0, ..., n\}$ that minimizes:
$$\frac{\sum_{i \in I} a_i}{\sum_{i \in I} b_i}$$
in an efficient way from the algorithmic point of view. Have you any ideas please?
[EDIT] SORRY: the cardinal of $I$ is a given value in the problem... let's call it $m$.

Hint:  suppose you have some subset $I$ with a ratio $\frac ab$ and add one more element to make a subset $I'$.  Does the ratio increase or decrease?
