Valued permutation Here is original problem.
Problem: there are 2 parallel arrays of positive floating point numbers A (Ai < 1000) and B (Bi < 1) of size n. 
How to find the minimal value for the following target function:
F(A, B) = Ak + Bk * F(A', B')
where A', B' denote the arrays A and B with their k:th element removed.
How to apply on such kind of problems, where we need to evaluate given function on a permutation?
Answers came up with some kind of heuristics, however we need optimal polynomial solution.
Anyone can suggest the approach for this?
 A: I would calculate $\frac{B_k-1}{A_k}$ and do those with smaller (including more negative) results on the most outside position of the recursion. 
This is at locally optimal in that you cannot swap a pair of adjacent choices and improve, and therefore globally optimal, since the algorithm gives a unique solution apart from equal values of $\frac{B_k-1}{A_k}$, which make no difference. Any other solution which does not have this property is not optimal.
If we compare $A_1+B_1\times (A_2+B_2\times F)$ with $A_2+B_2\times (A_1+B_1\times F)$ then the former will be smaller (or the same) iff 
$$ A_1+B_1(A_2+B_2 F) \le A_2+B_2(A_1+B_1 F)$$
$$ A_1+ B_1 A_2+B_1 B_2 F \le A_2+B_2 A_1+B_2 B_1 F $$
$$ B_1 A_2 - A_2 \le B_2 A_1 - A_1$$
$$ \frac{B_1-1}{A_1} \le \frac{B_2-1}{A_2}$$ 
noting $A_k >0$.
The value of the empty $F(,)$ does not matter, as it appears in the end multiplied by all the $B_k$.
A: 2ND EDIT: It appears that what's below was based on a misunderstanding of the problem. I thought one could permute the $A_i$ and the $B_i$ independently, whereas in fact it seems they are meant to be linked. That being the case, I suspect there is no algorithm significantly more efficient than just testing every permutation, which is to say, there is no efficient algorithm. But that's just a guess, I'm nowhere near being able to give a proof. 

So it looks like you wind up with $$A_1+A_2B_1+A_3B_1B_2+\cdots$$ The sequence $B_1,B_1B_2,B_1B_2B_3,\dots$ is decreasing, so I think you want it to decrease as slowly as possible, so take $B_1\ge B_2\ge B_3\cdots$. Then to make the most of the $A_i$, take $A_1\ge A_2\ge A_3\cdots$. 
Note that my subscripts are in reverse order; my $A_1$ is the last item chosen. 
EDIT: the procedure above maximizes, the problem was to minimize, so, back to the drawing board. Also, I acted as though the base case was 1, when it's actually zero. And not only that, I thought I was reversing the order of the $A_i$, but I wasn't. So, here's what you do: 
First, permute so $B_n$ is the largest of the $B_i$, because it's going to get multiplied by zero. Permute the other $B_i$ so that $B_1\le B_2\le\dots\le B_{n-1}$; that will minimize all the products of the $B_i$. Then, you want the biggest $A_i$ multiplying the smallest of the $B$-products, the smallest $A_i$ multiplying the biggest of the $B$-products, so permute the $A_i$ so that $A_1\le A_2\le A_3\le\dots\le A_n$. 
See the example worked out in the comments. 
