algorithm - 找出使总和最小的排列

Question

我有一个元素数组 [(A1, B1), ..., (An, Bn)](都是正 float 且 Bi <= 1)，我需要找到这样的元素最小化总和的排列 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 和 i+1 th 条款，所有其他人保持不变。此外，在交换之前和之后，两项都有一个因子 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是正数，我们可以忽略这个因素，只看 A s 和 B秒。我们得到

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]是一，则包含“一减去该变量”的项为零(所以如果 B[i] 是一，我们应该交换，但如果 B[i+1] 是一，我们应该交换)；如果两个变量都为一，则两项均为零。现在让我们假设两者都不等于一；然后我们可以进一步重写得到

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

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

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

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