给定数组形式的未排序整数集，找到所有可能的子集，其总和大于或等于const整数k， 例如： - 我们的集合是{1,2,3}，k = 2
可能的子集： -
{2},
{3},
{1,2},
{1,3},
{2,3},
{1,2,3}
我只能想到一个简单的算法，它列出了集合的所有子集，并检查子集的总和是否> = k，但是它的指数算法并且列出所有子集需要O（2 ^ N）。我可以使用动态编程在多项式时间内解决它吗？
给定数组形式的未排序整数集，找到所有可能的子集，其总和大于或等于const整数k， 例如： - 我们的集合是{1,2,3}，k = 2
可能的子集： -
{2},
{3},
{1,2},
{1,3},
{2,3},
{1,2,3}
我只能想到一个简单的算法，它列出了集合的所有子集，并检查子集的总和是否> = k，但是它的指数算法并且列出所有子集需要O（2 ^ N）。我可以使用动态编程在多项式时间内解决它吗？
列出所有子集将保持不变 O(2^N) 因为在最坏的情况下，您可能仍需要列出除空单之外的所有子集。
动态编程可以帮助您计算具有的集合数 sum >= K
您可以自下而上跟踪从范围汇总到某个值的子集数量 [1..K]。像这样的方法将是 O(N*K) 这对小的只是可行的 K。
动态编程解决方案的想法最好用一个例子来说明。考虑这种情况。假设您知道由第一组组成的所有组 i 你知道的那些元素 t1 总和 2 和 t2 总和 3。让我们说下一个 i+1 元素是 4。给定所有现有集合，我们可以通过附加元素来构建所有新集合 i+1 或者把它留下来。如果我们把它拿出去，我们就得到了 t1 总和为的子集 2 和 t2 总和为的子集 3。如果我们追加它，那么我们获得 t1 总和为的子集 6 （2 + 4）和 t2 总和到 7 （3 + 4）和一个包含just的子集 i+1 总和为4.这给了我们总和的子集数 (2,3,4,6,7) 由第一个组成 i+1 元素。我们一直持续到 N。
在伪代码中，这看起来像这样：
int DP[N][K];
int set[N];
//go through all elements in the set by index
for i in range[0..N-1]
//count the one element subset consisting only of set[i]
DP[i][set[i]] = 1
if (i == 0) continue;
//case 1. build and count all subsets that don't contain element set[i]
for k in range[1..K-1]
DP[i][k] += DP[i-1][k]
//case 2. build and count subsets that contain element set[i]
for k in range[0..K-1]
if k + set[i] >= K then break inner loop
DP[i][k+set[i]] += DP[i-1][k]
//result is the number of all subsets - number of subsets with sum < K
//the -1 is for the empty subset
return 2^N - sum(DP[N-1][1..K-1]) - 1
我可以使用动态编程在多项式时间内解决它吗？
不会。问题比@amit（在评论中）更难提及。找出是否存在与特定k相加的子集 子集和问题这是NP难的。相反，你要求 多少 解决方案等于特定的k，这是更难的类别 P＃。此外，您的确切问题稍微困难一些，因为您不仅要计算，而且要枚举k和目标<k的所有可能子集。
如果k为0，并且该集合的每个元素都是正数，那么您别无选择，只能输出每个可能的子集，因此该问题的下限是O（2ñ） - 产生输出所需的时间。
除非你知道更多关于你没有告诉我们的价值k的事情，否则没有更快的通用解决方案来检查每个子集。