给定n个整数的列表，求和大于或等于x的最小基数子集
给定一个数组形式的未排序（多）整数集，求其和大于或等于常量整数x的最小基数子集。
我们的集合是{4 5 8 10 10}，x=15，所以最小基数子集和
这个问题与以下问题相关但不同：给定一个n个整数的列表，找到大于X的最小子集和在前面的问题中，作者要求得到一个和最接近X的子集，这里我们想要任何子集
共有1个答案
有多项式时间算法来解决这个问题吗？
对事实上，暴力会让你得到你想要的结果。
- 对列表进行排序：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（n^2），这意味着检查整个列表。
可以将子集和的优化实例简化为该问题吗？
我不这么认为。为总和确定特定值与我们正在做的有点不同。例如，给定一个列表和两个不同的值，我们将对给定的问题执行完全相同的步骤。对于每种价值，唯一的区别是我们何时超越了自己的价值。对于子集和问题，对于每个值，我们可能会有非常不同的结果。
-
我只能想到一个朴素的算法，它列出集合的所有子集，并检查子集的和是否和是否最小，但它是一个指数算法，列出所有子集需要O(2^n)。我能用动态规划在多项式时间内求解吗？
-
我知道一个O（n2）soln，它能以更好的方式实现吗，因为数组中元素的数量限制非常大
-
我试着写一个代码，它接受一个介于1和1_000_000之间的整数，并返回一个比相同数字的整数大的最小整数，如果它不存在，则打印0。 举个例子 输入：156 输出165 输入330 输出0 输入27711 输出71127 我的问题是，下面的代码没有为其他输入返回正确的输出。 例如，在输入4231中，输出应该是4312。 我很难找到为每个输入返回正确输出的最佳算法。 TNX提前 }
-
我有一个大小为的整数值数组和一个给定的。 我想找到子序列的总数，使得每个子序列的元素总和小于。例如：设 ，，数组的元素为 ，则其总子序列为 作为- 但是，所需的子序列是: 也就是说，不被取，因为它的元素和是，这大于，即
-
给定一个有N个整数的数组A，我们需要找到子数组的最高和，使得每个元素小于或等于给定的整数X 示例：设 N=8 且数组为 [3 2 2 3 1 1 1 3] 。现在，如果 x=2，那么如果我们考虑 1 个基本索引，则通过求和 A[2] A[3] 来回答 4。如何在 O（N） 或 O（N*logN） 中执行此问题 目前，我通过检查每个可能的子阵列来采用O（N^2）方法。如何降低复杂性？
-
给定一个2D数组和一个数字。 问题：我们有一个矩阵，矩阵的每个单元格表示遍历该单元格的成本。我们从左上角开始，我们必须到达最后一个单元格（右下角）。我必须编写一个函数，返回到达而不超过的最大代价路径的代价。 如果找不到最大和小于或等于的路径，则返回，矩阵的值不能为负 解决方案：我尝试了很多代码，但没有一个返回我期望的结果。 我的第一个解决方案是在一个简单的数组中转换2D数组，并应用背包算法，但它不