可以使用Python优化此函数以在O（n）时间内运行吗？

Question

下面是一个场景

该函数接受一个n项权重数组和一个q容量数组。目标是根据每个箱子的容量确定每个箱子可以容纳的物品数量

我已经编写了以下函数，但我遇到的问题是，它在非常大的输入值上超时。请在下面查看：

def noItems(weights, capacities):
    number_of_items = 0
    result = []
    weight_sums = [sum(weights[0:w:1]) for w in range(1, len(weights) + 1)]

    for i in range(0, len(capacities)):
        for j in range(0, len(weight_sums)):
            if weight_sums[j] <= capacities[i]:              
                number_of_items = number_of_items + 1

        result.append(number_of_items)

        number_of_items = 0

    return(result)

更新：示例输入和输出

输入权重：[2,3,5,8,1,4,7]

输入容量：[10,20,18,1,40,4]

输入约束： 权重[i]>；1及<；1000 容量[i]>；1及<；10^9

输出：[3,5,4,0,7,1]

如何优化此函数以获得更快的运行时，从而使其不会在非常大的输入上超时

Answer 1

您可以在O(nlogn)时间内使用累积权重列表上的二进制搜索来解决此问题

from bisect import bisect_right

def noItems(weights, capacities):
    result = []

    # or you can use itertools.accumulate():
    weight_sums = [0] * (len(weights))
    weight_sums[0] = weights[0]
    for i in range(1, len(weights)):
        weight_sums[i] = weight_sums[i-1] + weights[i]

    for x in capacities:
        number_of_items = bisect_right(weight_sums, x)
        result.append(number_of_items)
    return(result)

we =  [2, 3, 5, 8, 1, 4, 7]
ca = [10, 20, 18, 1, 40, 4]
print(noItems(we, ca))
[3, 5, 4, 0, 7, 1]

O(n)仅适用于先前排序的容量