我特别想解决这个变化:
我有 50 个目标和 1 件武器。武器有一定的概率击中每个目标，每个目标需要一定的时间才能击中。我只需要成功命中1个目标就可以成功，如果我错过了49个目标，我保证能命中最后一个目标。我正在尝试找到击中目标的顺序，以最大限度地减少成功所需的时间。
一个有 3 个目标的例子:
Input: ([time to hit target, numerator of probability, denominator of probability])
targets = [[5, 1, 5], [10, 1, 2], [20, 1, 5]]
Output: (order of targets)
[1, 0, 2]
最佳时间计算如下:
T(1,0,2)
= (1/2)(10) + (1 - 1/2)(1/5)(10 + 5) + (1 - 1/2)(1 - 1/5)(20 + 10 + 5)
= 5 + 1.5 + 14
= 20.5 minutes
几天来，我一直在研究这个问题，作为一个有趣的练习，但找不到比像 O(N!) 规模的蛮力更好的解决方案。
我正在考虑一种分支定界算法来降低成本，但我还没有能够成功地设计出一种边界方法，即如何计算给定部分订单的最短可能时间和最大可能时间。
如有任何建议或帮助，我们将不胜感激!
最佳答案
让我们假设订单是固定的(以某种方式)。让我们仔细看看 2 个连续的目标(没有一个是最后一个)。假设瞄准时间是t1和 t2命中的概率是p1和 p2 ， 分别。我们可以看到，当且仅当 p1 * t1 + (1 - p1) * p2 * (t1 + t2) > p2 * t2 + (1 - p2) * p1 * (t1 + t2) 交换它们时，答案会得到改善。 , 这意味着 p2 * t1 > p1 * t2 .因此，在最佳答案中 p2 * t1 <= p1 * t2 , 或 t1 / p1 <= t2 / p2 .这个比较器定义了所有元素的顺序(我们不能陷入局部最小值，因为比较器是可传递的)。但是，如果这两个元素中没有一个是最后一个元素(因为我们保证会击中最后一个目标)，这也是正确的。
它给了我们一个简单的多项式解:
修复最后一个元素(
O(n)选项)。使用上述比较器对其余元素进行排序。更新答案。这部分工作在
O(n * log n)时间。带有0的元素概率应该单独处理(它们应该总是被推到最后)。
总时间复杂度为O(n^2 * log n) .
关于algorithm - 如何解决武器目标分配变体，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27724591/