We are given $2n$ positive integers $a_1,a_2\ldots,a_n$ and and $$b_1,b_2,\ldots,b_n$$ as input.
The question is to find a permutation $O$ on $\{1,2,\ldots,n\}$ that minimizes $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right).$$
For example, take $n = 3$, $a_1 = 10, a_2 = 1, a_3 = 100, b_1 = 10, b_2 = 100$, and $b_3 = 1$. If we take $O$ so that $O(1) = 1, O(2) = 3$, and $O(3) = 2$, we have $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right) = 1311.$$
The desired output is $O(1) = 3, O(2) = 1$, and $O(3) = 2$, which yields $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right) = 321.$$
Trying all possibility is exponential. How can I find an optimal permutation $O$?
