我有一个正整数数组 {a1, a2, ...., an}，我想找出满足以下条件的数组的所有可能子集：
(sum >= K)
其中 K 是一个正整数。我知道这个问题的解决方案是动态编程，但无法思考如何在这种情况下使用它。请帮忙。
PS：我并不完全需要所有子集，而是说形成所有子集的所有元素的乘积。
问问题
2740 次
1 回答
0
你的问题看起来类似于 0-1 背包问题，除了事情 - 通常这个限制是，那个总和必须小于K。
但是您列出了问题，限制在哪里，总和必须更大。
因此，例如，如果您找到子集，它的总和大于 K，那么您可以添加任何未包含在子集中的集合元素，这仍然是答案。假设，您的集合是 {a1, a2, a3, a4} 和 {a1} >= K。然后，您有 2^3 种方法可以将 a2、a3 和 a4 添加到您的子集中。
所以，这个问题看起来像指数问题，因为你需要列出所有可能的变化。
最坏的情况是，当 K = 0 时。并且您有 N 个大于 0 的元素。因此，您需要列出 2 ^ N 个子集。
于 2013-08-08T12:12:15.840 回答