algorithm - 有值(value)的排列

Question

问题:有2个平行的正值数组A和 B尺寸n .

如何找到以下目标函数的最小值:

F(A, B) = A<sub>k</sub> + B<sub>k</sub> * F(A', B')

哪里A' , B'表示数组 A和 B和他们的 k :删除第一个元素。

我在考虑动态规划方法，但没有成功。

如何应用于此类问题，我们需要在排列上评估给定函数？

Answer 1

最佳解决方案是计算 (B_k - 1)/A_k 并在递归的最外部位置执行那些具有更小(包括更多负数)结果的结果。

这是局部最优的，因为您不能交换一对相邻的选择并进行改进，因此是全局最优的，因为除了 (B_k-1)/A_k 的相等值之外，该算法给出了唯一的解决方案，这没有区别。任何其他不具备此属性的解决方案都不是最优的。

如果我们比较 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_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

注意 A_k > 0。

空的 F(,) 的值并不重要，因为它出现在最后乘以所有 B_k。