给定一个有限的实数排序集合，生成所有可能的子集，其总和<= k。

Question

我想知道是否存在解决此问题的算法。这与背包0-1问题或幂集问题有些相似，但又不同。

给定一组有限的已排序实数，我们需要生成所有可能的子集，其和小于等于k。这里k是实数，已排序的实数都为正数。例如，一个数组={1.48, 2.21, 3.07, 4.35, 4.46}，k=5.94。输出结果为：{4.46}，{4.46, 1.48}，{4.35}，{4.35, 1.48}，{3.07}，{3.07, 2.21}，{2.21}，{2.21, 1.48}和{1.48}。

解决这个问题的一种方法是从最高的数字{4.46}开始遍历，看你可以在篮子里包含多少个数字，然后继续下一个较低的数字 {4.35}等等。有没有一种有效的方法来做到这一点？请告诉我。

- SpiderMath

---

输入是否为实数？或者是浮点数？还是定点数？pi或sqrt(2)是否合法？ - amit

另外相关的是，对于整数而言，找到一个子集，其总和恰好为 k 是 子集和问题，这是 NP-难问题。 - amit

是的，假设这是一个固定点...想象一下我们取π或sqrt(2)，并将其截断为4位小数。是的，如果我们假设它是整数，找到总和恰好为k的子集就是子集和问题，可以用动态规划来解决。 - SpiderMath

Answer 1

贪心算法肯定有效。为了利用输入已排序的事实，可以使用二分查找。

基本思路是：首先通过二分查找搜索数组中最大的小于K的数字，将结果元素推入堆栈，然后递归地搜索以该元素结尾的子数组，寻找值为K-该元素值的和。完成此操作后，在子数组中搜索和K以覆盖未选择该元素的情况。

示例代码：

void boundedSumSubarray(float * arr, int size, float K, stack S) {
    int pos=binarySearch(arr,size,K);
    if (pos>=0) {
        pushStack(S,arr[pos]);
        boundedSumSubarray(arr,pos-1,K-arr[pos],S);
        popStack(S);
        boundedSumSubarray(arr,pos-1,K,S);
    } else
        printStack(S);
}

- HelloWorld

Answer 2

你需要“生成”所有子集，而不是“计算”所有子集。这样做会使工作变得更容易 :)

令 F(x,y,k) 为 x[1:k] 的子集集合，其总和小于 y。

F(x,y,k+1) = F(x,y,k) \union { for each set g in F(x,y-x[k+1], k): g \union {k+1} }

使用以上递归方法生成所有这样的情况。

请注意，在执行F(x,y-x[k+1], k)时，您无需实际重新计算子集集合。只需将列表保留在树形结构中即可。

如果您期望的子集数量为m，则此算法的时间复杂度为O(nm)。

- ElKamina