algorithm - 找到元素小于 S 的子集

Question

我必须找到解决以下问题的算法:

输入是两个自然数 S 和 k 以及一组未排序的 n 对不同数。

在 O(n) 中确定是否存在 k 个数的子集总和 <=S。注意:k不应该是时间复杂度的一部分。

algorithm({x_1, ..., x_n}, k, S):
    if exists |{x_i, ..., x_j}| = k and x_i + ... x_j <= S return true

我没有找到时间复杂度为 O(n) 的解决方案。

我能得到的是 O(kn)，因为我们搜索最小值的 k 倍，求和:

algorithm(a={x_1, ..., x_n}, k, S):
    sum = 0
    for i=1,...,k:
        min = a.popFirst()
        for i=2,...,len(a):
            if(a[i] < min):
                t = a[i]
                a[i] = min
                min = t
        sum += min
    if sum <= S:
        return true
    else:
        return false

这是在 O(n) 中并返回正确的结果。我怎样才能松开 k？

谢谢你帮助我，我真的很纠结这个问题!

Answer 1

Quickselect 可用于查找 k 个最小元素:https://en.wikipedia.org/wiki/Quickselect

它基本上是快速排序，只是您只在主元感兴趣的一侧递归。

一个简单的实现在 O(N) 预期 时间内运行，但是使用中位数中位数来选择一个枢轴，您可以使它成为真正的最坏情况绑定(bind):https://en.wikipedia.org/wiki/Median_of_medians