找到一个最小化总和的排列

Question

我有一个元素数组< code>[(A1，B1)，...，(An，Bn)](都是正浮点和Bi

毫无疑问，我可以尝试所有这些方法，并选择一个给出最小和的方法(这将给出正确的结果O(n！)).

我尝试将总和更改为A1 B1*（A2 B2*（A3 B3*（… B（n-1）*AN））并尝试使用贪婪算法，该算法在每个步骤上获取最大的Ai元素（这不会产生正确的结果）。

现在，当我看最新的方程时，我觉得这里我看到了最优子结构A（n-1）B（n-1）*An，因此我必须使用动态编程，但我无法找出正确的方向。有什么想法吗？

Answer 1

我认为这可以在O（N log（N））中解决。

任何置换都可以通过交换相邻元素对来获得；例如，这就是气泡排序工作的原因。因此，让我们看看交换条目（a[i]，B[i]）和（a[i 1]，B[1]）的效果。我们想知道在哪些情况下进行这种交换是一个好主意。这仅对ith和i1th项有效，所有其他项保持不变。此外，在交换之前和之后，这两个术语都有一个因子B[1]*B[2]*…*B[i-1]，我们现在可以称其为CC是正数。

在交换之前，我们正在处理的两个术语是 C*A[i] C*B[i]*A[i 1]，之后它们是 C*A[i 1] C*B[i 1]*A[i]。如果两者之间的差异为正，则这是一个改进：

C*(A[i] + B[i]*A[i+1] - A[i+1] - B[i+1]*A[i]) > 0

由于C是正的，我们可以忽略该因素，只查看As和Bs。我们得到

A[i] - B[i+1]*A[i] > A[i+1] - B[i]*A[i+1]

或者等同地

(1 - B[i+1])*A[i] > (1 - B[i])*A[i+1]

这两个表达式都是非负的；如果< code>B[i]或< code>B[i 1]中的一个是1，则包含“1减去该变量”的项是0(因此，如果< code>B[i]是1，我们应该交换，但如果< code>B[i 1]是1，则不交换)；如果两个变量都是一，那么两项都是零。现在让我们假设两者都不等于一；然后我们可以进一步重写以获得

A[i]/(1 - B[i]) > A[i+1]/(1 - B[i+1])

因此，我们应该计算这两项的表达式< code>D[i] := A[i]/(1 - B[i])，如果左边的大于右边的，就交换它们。在这种情况下，我们可以通过将< code>D[i]定义为无限大，将这种情况扩展到一个或两个< code>B为一的情况。

好的，让我们回顾一下-我们发现了什么？如果存在一对i，i 1，其中

计算所有D[i]值可以在一次线性时间内完成。排序可以使用O（N log（N））算法完成（我们只需要将相邻元素的交换作为参数/证明，以表明这是最佳解决方案，而不是实现的一部分）。