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

Question

我有一个元素数组[(A1, B1), ..., (An, Bn)]（全部都是正浮点数且 Bi <= 1），我需要找到这样的排列来最小化 sum A1 + B1 * A2 + B1 * B2 * A3 + ... + B1 * ... B(n-1) * An。

当然，我可以尝试所有这些并选择给出最小总和的一个（这将在 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[i+1])。我们想知道在什么情况下进行这种交换是个好主意。i这仅对第th 项和第 th 项有效i+1，所有其他项保持不变。此外，在交换之前和之后，两项都有一个因子B[1]*B[2]*...*B[i-1]，我们C现在可以调用它。C是一个正数。

在交换之前，我们处理的两个术语是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]

这两个表达式都是非负的；如果 或 之一B[i]是B[i+1]一，则包含“一减去该变量”的项为零（因此我们应该交换 if B[i]is 1 而不是 if B[i+1]is 1）；如果两个变量都为 1，则两项都为零。现在我们假设两者都不等于 1；那么我们可以进一步重写以获得

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

因此，我们应该计算这D[i] := A[i]/(1 - B[i])两项的表达式，如果左侧项大于右侧项，则交换它们。B我们可以通过定义将其扩展到其中一个或两个 s 为 1 的情况D[i]，方法是将其定义为无限大。

好吧，让我们回顾一下——我们发现了什么？如果存在一对i, i+1where D[i] > D[i+1]，我们应该交换这两个条目。这意味着我们无法通过交换来改进结果的唯一情况是当我们对这些对重新排序以使值D[i]按递增顺序排列时——也就是说，所有情况都排在B[i] = 1最后（回想一下，这对应于D[i]无限大） ），否则按价值递增顺序D[i]。我们可以通过按值排序来实现这一点D[i]。快速检查我们上面的步骤表明，具有相等的对的顺序D[i]不会影响最终值。

计算所有D[i]值可以在单个线性时间过程中完成。排序可以通过算法来完成O(N log(N))（我们需要交换相邻元素的东西仅作为参数/证明来表明这是最佳解决方案，而不是作为实现的一部分）。