我有一个元素数组[(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，因此我必须使用动态编程，但我无法弄清楚正确的方向。有什么想法吗？
我认为这可以在O(N log(N))解决。
任何置换都可以通过交换相邻元素对来获得;例如，这就是为什么冒泡排序有效。那么让我们来看看交换条目(A[i], B[i])和(A[i+1], B[i+1])的效果。我们想知道在哪些情况下进行交换是个好主意。这只对i 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是积极的，我们可以忽略的因素，并期待只是在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]之一是1，那么包含'one minus the variable'的项是零（因此如果B[i]是1，则我们应该交换，但如果B[i+1]是1，则不应该交换）;如果两个变量都是1，那么这两个项都是零。现在我们假设两个都不等于一个;那么我们就可以进一步改写为获得
A[i]/(1 - B[i]) > A[i+1]/(1 - B[i+1])
因此，我们应该计算这个表达式D[i] := A[i]/(1 - B[i])两个术语和交换它们如果左边一个是比右边的大。我们可以将其扩展到一个或两个B s是通过将D[i]定义为无限大的情况。
好的，让我们回顾一下 - 我们发现了什么？如果有一对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))算法完成（我们需要交换相邻元素的东西只作为参数/证明，以表明这是最佳解决方案，而不是实现的一部分）。
谢谢，这是一个很好的解释。在你描述它之后，它看起来很容易:-)。任何有助于你提出这个想法的见解？ – 2014-12-09 06:28:03
另外我找不到你的推理中的缺陷，下面的输出A，B = [89,80,62,34,19]，[0.80,0.74,0.9,0.25,0.5]产生了错误的结果：61.5705与（34，19，80，89，62），而最小值是58.8205，它是用（19,34,80,89,62） – 2014-12-09 07:23:14
哎呀！我误解了，并认为第i项包括了“B [i]”的因素。同样的想法仍然有效，它只是略微改变了D [i]的定义。我会稍微改写一下我的答案。 – 2014-12-09 15:09:20
不失一般让我们假设An> = An-1 ...。 > = A2> = A1如果Bi具有相同的序列，则答案显然是A1 + B1 A2 + B1 B2 A3 + ...。 。 在一切都不那么容易，Bi没有像Ai那样相同的序列的情况下，我认为没有办法在多项式时间内找到最佳答案，也许您可以在多项式中找到近似最好的答案贪婪或DP的时间，但你无法在多项式时间中找到确切的最小答案。 – Lrrr 2014-12-07 07:27:06
@AliAmiri否，如果An> An-1并不意味着Bn> Bn-1，并且我确定存在针对此问题的多项式解决方案，因为我必须为相当大量的数据执行此操作。 – 2014-12-07 08:01:56
目前我在工作，也不记得NP-问题映射方法非常好，但我认为它可以证明是NP，但我认为有很多修改，你可以做，并减少运行时间。但我希望我错了，这不是NP :) – Lrrr 2014-12-07 08:10:22