Return to Answer

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.

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 $i\in S \Rightarrow j \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 $i$ to $j$ iff $i\in S \Rightarrow j \in S$. Originally I presented a wrong proof where the graph had an edge between any two vertices and one could continue with that.

I have a very bad but polynomial time algorithm: 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$. For $i,j \in [n]\backslash S$ with $b_j>b_i$ we have $$c_{S\cup i}=\frac{a_S+a_i}{b_Sb_i}>\frac{a_S+a_j}{b_Sb_j}=c_{S\cup j} \Leftrightarrow a_S>\frac{a_jb_i-a_ib_j}{b_j-b_i}.$$ We compute the values $\frac{a_jb_i-a_ib_j}{b_j-b_i}$ for all pairs $(i,j)$. This values divide $\mathbb{R}$ into maximal $\binom{n}{2}+1$ many intervals. We loop through all this intervals and assume each time that $a_S$ lies in this interval. For each pair $(i,j)$ we get a rule as follows $i\in S\Rightarrow j\in S$ (or vice versa). Let $i\in [n]$ be such that the number of $j\in [n]$ such that $i \in S\Rightarrow j\in S$ is maximal. It follows that if $i\in S$ then $S=[n]$. By Induction we compute the optimal set from $[n]\backslash i$ and its value compare it with $c_{[n]}$.

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.

I have a very bad but polynomial time algorithm: 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$. For $i,j \in [n]\backslash S$ with $b_j>b_i$ we have $$c_{S\cup i}=\frac{a_S+a_i}{b_Sb_i}>\frac{a_S+a_j}{b_Sb_j}=c_{S\cup j} \Leftrightarrow a_S>\frac{a_jb_i-a_ib_j}{b_j-b_i}.$$ Now compute the fractions $\frac{a_jb_i-a_ib_j}{b_j-b_i}$ for all pairs $i,j$. The values divide $\mathbb{R}$ into maximal $\binom{n}{2}+1$ many intervals. We loop through all this intervals and assume each time that $a_S$ lies in this interval. For each pair $(i,j)$ we get a rule as follows $i\in S\Rightarrow j\in S$ (or vice versa). We can then find $i\in [n]$ such that if $i\in S$ then $S=[n]$. By Induction we compute the optimal set from $[n]\backslash i$ and compare it with the set $[n]$.

I have a very bad but polynomial time algorithm: 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$. For $i,j \in [n]\backslash S$ with $b_j>b_i$ we have $$c_{S\cup i}=\frac{a_S+a_i}{b_Sb_i}>\frac{a_S+a_j}{b_Sb_j}=c_{S\cup j} \Leftrightarrow a_S>\frac{a_jb_i-a_ib_j}{b_j-b_i}.$$ We compute the values $\frac{a_jb_i-a_ib_j}{b_j-b_i}$ for all pairs $(i,j)$. This values divide $\mathbb{R}$ into maximal $\binom{n}{2}+1$ many intervals. We loop through all this intervals and assume each time that $a_S$ lies in this interval. For each pair $(i,j)$ we get a rule as follows $i\in S\Rightarrow j\in S$ (or vice versa). Let $i\in [n]$ be such that the number of $j\in [n]$ such that $i \in S\Rightarrow j\in S$ is maximal. It follows that if $i\in S$ then $S=[n]$. By Induction we compute the optimal set from $[n]\backslash i$ and its value compare it with $c_{[n]}$.