找到最小化总和的排列

Question

找到最小化总和的排列

algorithmdata-structuresdynamic-programming

3

我有一个由元素组成的数组[(A1,B1),...(An,Bn)]（均为正浮点数，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，因此我必须使用动态规划，但我无法确定正确的方向。有什么想法吗？

- Salvador Dali

不失一般性，假设An>=An-1….>=A2>=A1。如果Bi具有相同的顺序，则答案显然是A1+B1 A2+B1 B2 A3+…。如果情况并非如此简单，Bi与Ai的顺序不同，那么我认为没有办法在多项式时间内找到最佳答案，也许你可以用贪心或DP在多项式时间内找到近似最佳答案，但你无法在多项式时间内找到确切的最小答案。 - Lrrr

@AliAmiri 不，如果An> An-1并不意味着Bn> Bn-1，而且我相当确定这个问题有一个多项式解决方案，因为我需要处理大量的数据。 - Salvador Dali

目前我正在工作，而且我不太记得 NP 问题映射方法，但我认为它可以被证明是 NP，但我认为你可以做很多修改并减少运行时间。但我希望我错了，这不是 NP :) - Lrrr

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Erik P. · Accepted Answer

我认为这可以在 O(N log(N)) 的时间复杂度内解决。

通过交换相邻元素对，我们可以获得任何排列；例如冒泡排序就是这个原理。所以让我们来看看交换条目 (A[i], B[i]) 和 (A[i+1], B[i+1]) 的影响。我们想找出什么情况下进行此交换是一个好主意。这只会对第 i 项和第 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 是正数，我们可以忽略该因子仅关注 A 和 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]为1，则包含“这个变量减1”的项为0（因此，如果B[i]为1但B[i+1]不为1时应进行交换）；如果两个变量都为1，则两个项都为0。暂时假设它们都不等于1；那么我们可以进一步重写以获得

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

因此，我们需要计算这个表达式D[i] := A[i]/(1 - B[i])的两个术语，并且如果左边的大于右边的，则交换它们。我们可以通过在这种情况下将D[i]定义为无限大来将其扩展到一个或两个B都为1的情况。

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

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