给定一个数组形式的未排序(多(整数集，找到其和大于或等于常量整数x的最小基数子集。
例如：-我们的集合是｛4 5 8 10 10｝并且x＝15，因此sum>x是｛5 10｝
有多项式时间算法来解决这个问题吗？可以将子集和的优化实例简化为该问题吗？
这个问题与以下问题有关但不同：给定一个n个整数的列表，在前面的问题中找到大于X的最小子集和，作者要求求和最接近X的子集，这里我们想要任何子集>x，但具有最小数量的元素
有多项式时间算法可以解决这个问题吗？
是。事实上，暴力会给你带来你想要的结果。
- 对列表进行排序：O(n log n(
- 从最大值的末尾开始(任意一端取决于排序方式(即升序或降序((并添加值，直到达到目标：O(n(
总体而言，该算法具有O(n log n(复杂度，其存在于多项式时间内。
可能有更好的算法，但我不确定。我知道在O(n(时间中可以找到nth最大值，但您必须执行m次，其中>m表示最小基数。因此，对于这种方法，总体复杂度是O(m*n(，它仍然是多项式。
第一种方法给出O(n log n(，而不管最小基数的大小。第二种方法给出了更好的最佳情况(即基数最终为1，这意味着总体复杂度为O(n((，但最坏的情况是O。
可以将子集和的优化实例简化为该问题吗？
我不这么认为。针对总和的特定值与我们正在做的有点不同。例如，给定一个列表和两个不同的值，我们将对给定的问题执行完全相同的步骤。对于每一个价值，唯一的区别是我们何时超越了自己的价值。对于子集和问题，我们可能会对每个值产生截然不同的结果。