Edit: Original proof was wrong and I couldn't fix it. The algorithm does not work in general. 

For $S\subset [n]$ let $a_S=\sum_{i\in S} a_i$, $b_S=\prod_{i\in S} b_i$ and $c_S=a_S/b_S$. If $S$ is optimal, $i \in S$ and $j\in [n]\backslash S$ we have
$$\frac{a_S}{b_S}=c_{S}\geq c_{(S\backslash i)\cup j}=\frac{a_S-a_i+a_j}{b_Sb_j/b_i}$$
Hence $a_S(b_j-b_i)\geq b_i(a_j-a_i)$ and therefore
$$\begin{cases} a_S\geq \frac{(a_j-a_i)b_i}{b_j-b_i} & \text{if } b_i>b_j\\ a_S\leq\frac{(a_j-a_i)b_i}{b_j-b_i} & \text{if } b_i<b_j\\ a_j\leq a_i & \text{if }b_i=b_j\end{cases}.$$
The values $\frac{(a_j-a_i)b_i}{b_j-b_i}$ for all pairs $(i,j)\in [n]^2$ divide $\mathbb{R}$ into maximal $2\binom{n}{2}+1$ many intervals. We loop through all these intervals and assume each time that $a_S$ lies in the corresponding interval. If an inequality above is violated we get that $j\in S \Rightarrow i \in S$. We consider a directed graphs with vertex set $[n]/\sim$ with $i\sim j$ iff $(a_i,b_i)=(a_j,b_j)$ and a edge from $j$ to $i$ iff $j\in S \Rightarrow i \in S$. Originally I presented a wrong proof where the graph had an edge between any two vertices and one could continue with that.