比python中嵌套循环更快的搜索方式

Question

我在寻找一个数组的最小期望成本的最优次序。在

输入是：

input = [[390, 185, 624], [686, 351, 947], [276, 1023, 1024], [199, 148, 250]]

这是一个由四个选项组成的数组，第一个数字是成本，第二个数字是获得结果的概率，第一个（[i][1]）是分子，第二个（[i][2]）是分母。在

目标是找到这些值/概率对的最佳顺序，以最少的总成本提供结果。在

^{pr2}$

运行中：

print answer(input)

应该回来

[2, 3, 0, 1]

对于给定的输入。在

这显然是一个详尽的搜索，在超过四个选项的情况下，搜索速度非常慢。我认为二叉搜索树是非常相似的输入，但是我不知道如何实现它。在

我已经花了四天的时间来研究这个问题，但似乎无法找到一个对任何输入都有效的快速版本（假设成本和概率是正的）。在

这不是做作业什么的，只是个我一直想弄明白的谜题。在

Answer 1

我将确定原始数组中每个事例的值，存储这些值，然后对列表进行排序。这是在Python3中，所以我不知道这是否会影响到你。在

确定原始数组中每个事例的值并存储它们：

inputA = [[390, 185, 624], [686, 351, 947], [276, 1023, 1024], [199, 148, 250]]
results = []
for idx,val in enumerate(inputA):
    results.append((val[0]*val[1]/val[2], idx))

对列表进行排序，提取位置：

^{pr2}$

迭代列表是O(n)，排序是O(nlogn)。Map/list/print对O(n)再次进行迭代，因此性能应该是O(nlogn)。在