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$.
 A: $O(n^2)$ is not too hard, here is an inductive approach.
Induction is on n, keeping m constant.
Base case: if n = m, then pick all i for I.
Inductive case:
Suppose I have the best subset S till n-1. Either S is still the best for n, or I have to replace one of the elements in S by n. I can evaluate all these options in O(n) time by pre-computing sums of as and bs for S.
$T(n) = T(n-1) + O(n)$ gives $T(n) = O(n^2)$
EDIT: To prove correctness, most cases are already explicitly dealt with. We just have to exclude the possibility that the best set containing n is not one of the candidates we have obtained here.
Suppose the sum of a's from the (n-1) case is a, and the sum of the b's there be b.
Suppose the sums obtained by this process after the inductive step are (a+p, b+q).
Suppose there exist some bad set like this. Suppose the numerator of the actual least ratio here is (a+p+s) and the denominator is (b+q+r).
We want to prove that if $\frac{a}{b} \lt \frac{a+s}{b+t}$ then $\frac{a+p}{b+q} \lt \frac{a+p+s}{b+q+t}$
The first condition is equivalent to $\frac{a}{b} \lt \frac{s}{t}$ while the second one is equivalent to $\frac{a+p}{b+q} \lt \frac{s}{t}$. However, $\frac{a+p}{b+q} \lt \frac{a}{b}$ by construction so if the first condition holds then second one does too.
The reason why simple sorting does not work is because the conditions on the ratios are on the values s, t, p, q which are of the form (sum of elements in A-B) - (sum of elements in B-A), not on the a's and b's themselves. This approach takes care of that.
A: 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?
