给定一个包含 n 个整数的列表，找到总和大于或等于 x 的最小基数子集
Given a list of n integers, find the minimum cardinality subset with sum greater than or equal to x
给定数组形式的一组未排序（多）整数，找到总和大于或等于常量整数 x 的最小基数子集。
例如：- 我们的集合是 {4 5 8 10 10} 和 x=15 所以总和 >=x 的最小基数子集是 {5 10}
有多项式时间算法可以解决这个问题吗？是否可以将子集和的优化实例简化为该问题？
本题与以下问题相关但不同： 上一题中，作者要求求和最接近x的子集，这里要任意>=x但最小的子集元素数量
Is there a polynomial time algorithm to solve this problem?
是的。事实上，蛮力会让你得到你想要的结果。
- 对列表进行排序：O(n log n)
- 从最大值的末尾开始（哪一端取决于您的排序方式（即升序或降序））并添加值直到达到目标：O (n)
总的来说，这个算法有 O(n log n) 的复杂度，在多项式时间内。
可能有更好的算法，但我不确定。我知道可以在 nth 中找到最大值 O(n) 次，但是您必须执行此 m 次，其中 m表示最小基数。因此，对于这种方法，总体复杂度为 O(m * n)，这仍然是多项式。
无论最小基数的大小如何，第一种方法都会给出 O(n log n)。第二种方法给出了更好的 best 情况（即基数最终为 1，这意味着整体复杂度为 O(n))，但是最坏的情况是 O(n^2)，这意味着整个列表都被检查了。
Can one reduce an optimization instance of subset sum into that problem?
我不这么认为。针对总和的特定值与我们正在做的有点不同。例如，给定一个列表和两个不同的值，我们将对给定的问题执行完全相同的步骤。对于每个价值，唯一的区别是我们何时超越了我们的价值。对于子集求和问题，每个值的结果可能大相径庭。
给定数组形式的一组未排序（多）整数，找到总和大于或等于常量整数 x 的最小基数子集。
例如：- 我们的集合是 {4 5 8 10 10} 和 x=15 所以总和 >=x 的最小基数子集是 {5 10}
有多项式时间算法可以解决这个问题吗？是否可以将子集和的优化实例简化为该问题？
本题与以下问题相关但不同：
Is there a polynomial time algorithm to solve this problem?
是的。事实上，蛮力会让你得到你想要的结果。
- 对列表进行排序：O(n log n)
- 从最大值的末尾开始（哪一端取决于您的排序方式（即升序或降序））并添加值直到达到目标：O (n)
总的来说，这个算法有 O(n log n) 的复杂度，在多项式时间内。
可能有更好的算法，但我不确定。我知道可以在 nth 中找到最大值 O(n) 次，但是您必须执行此 m 次，其中 m表示最小基数。因此，对于这种方法，总体复杂度为 O(m * n)，这仍然是多项式。
无论最小基数的大小如何，第一种方法都会给出 O(n log n)。第二种方法给出了更好的 best 情况（即基数最终为 1，这意味着整体复杂度为 O(n))，但是最坏的情况是 O(n^2)，这意味着整个列表都被检查了。
Can one reduce an optimization instance of subset sum into that problem?
我不这么认为。针对总和的特定值与我们正在做的有点不同。例如，给定一个列表和两个不同的值，我们将对给定的问题执行完全相同的步骤。对于每个价值，唯一的区别是我们何时超越了我们的价值。对于子集求和问题，每个值的结果可能大相径庭。