Valued permutation

Question

Problem: there are 2 parallel arrays of positive values A and B 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.

I was thinking about dynamic programming approach, but with no success.

How to apply on such kind of problems, where we need to evaluate given function on a permutation?

Answer 1

The optimal solution is to calculate (B_k - 1)/A_k and do those with smaller (including more negative) results on the most outside position of the recursion.

This is 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 (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*(A_2+B_2*F) with A_2+B_2*(A_1+B_1*F) then the former will be smaller (or equal) iff

A_1 + B_1*(A_2 + B_2*F) <= A_2 + B_2*(A_1 + B_1*F)
A_1 + B_1*A_2 + B_1*B_2*F <= A_2 + B_2*A_1 + B_2*B_1*F
B_1*A_2 - A_2 <= B_2*A_1 - A_1
(B_1 - 1)/A_1 <= (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.

Answer 2

I've come up with a heuristic. Too bad it is not optimal (thanks yi_H!) =(

At first, I thought that starting with increasing values of A_i. However, counterexamples remained (A={1000, 900} and B={0.1, 0.5}) So I came up with this :

For each value of i in [1..n], compute V_i = A_i + B_i*min(A_j) for j!=i

Choose i such that V_i is the smallest among all the V values. Remove A_i and B_i from A and B. These are the two first terms.

Repeat with A' and B' until the end (until both are empty).

The algorithm is O(n^2) if you memorize the V_i and update them, otherwise it's O(n^3) for a naive implementation.

Edit : Congrats for yi_H for finding counter-examples showing why this is non optimal!