algorithm - 最小总和大于或等于 k ​​的子集

Question

我正在尝试编写一个 python 算法来执行以下操作。给定一组正整数 S，找到总和最小且大于或等于 k ​​的子集。

例如:S = [50, 103, 85, 21, 30]k = 140

子集 = [85, 50, 21](总和 = 146)

初始集合中的数字都是整数，k可以任意大。通常集合中会有大约 100 个数字。

当然有遍历所有可能子集的蛮力解决方案，但它在 O(2^n) 中运行，这是不可行的。有人告诉我这个问题是 NP-Complete，但应该有一种动态规划方法允许它在伪多项式时间内运行，就像背包问题一样，但到目前为止，尝试使用 DP 仍然引导我找到解决方案是 O(2^n)。

有没有办法把DP应用到这个问题上？如果是这样，如何？我发现 DP 很难理解，所以我可能漏掉了一些东西。

非常感谢任何帮助。

Answer 1

看到数字不是整数而是实数，我能想到的最好的是 O(2^(n/2) log (2^(n/2))。

乍一看可能更糟，但请注意 2^(n/2) == sqrt(2^n)

因此，为了实现这种复杂性，我们将使用称为中间相遇的技术:

1. 将集合分成两部分，大小分别为 n/2 和 n-n/2
2. 使用暴力生成所有子集(包括空子集)并将它们存储在数组中，我们称它们为A和B
3. 让我们对数组 B 进行排序
4. 现在对于 A 中的每个元素 a，如果 B[-1] + a >=k 我们可以使用二进制搜索找到最小的元素 b 在 B 中满足 a + b >= k
5. 在我们找到的所有这样的 a + b 对中选择最小的

---

OP 现在稍微改变了问题的整数，所以这里是动态解决方案:

好吧，经典背包。

对于 [1,n] 中的每个 i，我们有 2 个选项来设置项目 i: 1. 包含在子集中，状态从(i, w)变为(i+1, w + S[i]) 2.跳过它，状态从(i, w)变为(i+1, w)

每当我们到达某个 w >= k 时，我们更新答案

伪代码:

visited = Set() //some set/hashtable object to store visited states
S = [...]//set of integers from input
int ats = -1;

 void solve(int i, int w) //theres atmost n*k different states so complexity is O(n*k)
{
    if(w >= k)
    {
        if(ats==-1)ats=w;
        else ats=min(ats,w);
        return;
    }
    if(i>n)return;

    if(visited.count(i,w))return; //we already visited this state, can skip
    visited.insert(i,w)=1;

    solve(i+1, w + S[i]); //take item
    solve(i+1, w); //skip item
}

solve(1,0);
print(ats);