algorithm - 如何在O(n)时间内选择最少数量的权值得到总权值

Question

如果有 n 个未排序的权重，我需要找到最少数量的权重以获得至少 W 的权重。我如何在 O(n) 中找到它们？

Answer 1

这个问题有很多解决方法:

方法 1 - 排序 - O(nlogn)
我想最简单的方法是按降序排序，然后取总和至少为 W 的前 K 个元素。时间复杂度将是 O(nlogn)。

方法 2 - 最大堆 - O(n + klogn)
另一种方法是使用最大堆。创建堆将花费 O(n) 然后提取元素直到我们得到至少 W 的总和。每次提取将花费 O(logn) 所以总时间复杂度将为 O(klogn)，其中 k 是我们必须从堆中提取的元素数。

方法 3 - 使用最小堆 - O(nlogk)
添加此方法 JimMischel在下面的评论中提出建议。
使用列表中的前 k 元素创建一个最小堆，该元素总和至少为 W。然后，遍历剩余的元素，如果它大于最小值(堆顶)，则在它们之间进行替换。
在这一点上，我们可能有更多的元素来达到 W，所以我们将只提取最小值，直到达到我们的限制。在实践中，取决于

之间的关系

find_min_set(A,W)
    currentW = 0
    heap H //Create empty heap

    for each Elem in A
        if (currentW < W)
            H.add(Elem)
            currentW += Elem
        else if (Elem > H.top())
            currentW += (Elem-H.top())
            H.pop()
            H.add(Elem)

    while (currentW-H.top() > W)
        currentW -= H.top()
        H.pop()

根据 k 和 n 之间的关系，这种方法在实践中可能会更快。参见 when theory meets practice .

方法 4 - O(n)
我能想到的最好的方法是使用某种 quickselect同时跟踪总重量并始终以中位数作为支点进行分区。

首先，让我们定义一些东西:

sum(A) - 数组 A 中所有元素的总和。
num(A) - 数组 A 中的元素数。
med(A) - 数组 A 的中位数。

find_min_set(A,W,T)
    //partition A
    //L contains all the elements of A that are less than med(A)
    //R contains all the elements of A that are greater or equal to med(A)
    L, R = partition(A,med(A))
    if (sum(R)==W)
        return T+num(R)
    if (sum(R) > W)
        return find_min_set(R,W,T)
    if (sum(R) < W)
        return find_min_set(L,W-sum(R),num(R)+T)

通过find_min_set(A,W,0)调用此方法。

运行时复杂度:

• 寻找中位数是 O(n)。
• 分区是 O(n)。
• 每个递归调用占用数组大小​​的一半。
• 总结起来我们得到一个跟随关系:T(n) = T(n/2) + O(n) 这与 quickselect = O 的平均情况相同(n).

注意:当所有值都是唯一的时，最坏情况和平均复杂度确实是O(n)。对于可能的重复值，平均复杂度仍然是 O(n) 但最坏的情况是 O(nlogn) 使用 Median of medians选择枢轴的方法。