1

我正在尝试编写一个 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 很难理解，所以我可能错过了一些东西。

任何帮助深表感谢。

4

1 回答 1

-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我们可以使用二进制搜索找到bB 中满足的最小元素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)

每次我们达到某个 >= k 的 w 时，我们都会更新答案

伪代码：

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);
于 2019-05-08T16:44:44.533 回答