给定有限的一组有序实数产生所有可能的子集，其总和<= k

我想知道是否存在解决此问题的算法。它与背包0-1问题稍微相似，或者功率设置问题不同。给定有限的一组有序实数产生所有可能的子集，其总和<= k

给定有限的一组有序实数，我们需要生成所有可能的子集，其总和为< = k。这里k是真实的，排序后的实数都是正数。例如，数组= {1.48,2.21,30.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}等等。有没有一种有效的方法来做到这一点？让我知道

来源

2012-03-23 SpiderMath

输入是真的实数还是浮点数？或固定点？是'pi'还是'sqrt（2）'法律要素？ – amit 2012-03-23 18:29:07

也相关：对于整数，找到一个子集，其中恰好*到'k'是[子集和问题]（http://en.wikipedia.org/wiki/Subset_sum_problem），它是NP-Hard。 – amit 2012-03-23 18:33:02

是的，让我们假设这是固定点...想象一下，我们采用pi或sqrt（2），我们可以截断它到4位小数位。是的，如果我们假设它是整数，找到与k恰好相加的子集是动态规划解决的子集和问题 – SpiderMath 2012-03-25 00:19:56

贪婪算法绝对可以工作。为了利用输入被排序的事实，可以使用二进制搜索。

其基本思想是：首先通过二分搜索搜索数组中最大的数字小于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); 
}

来源

2012-03-23 18:51:50 HelloWorld

您需要“生成”所有的子集，而不是“计数”的所有子集。这使得工作变得更容易:)

设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）。

来源

2012-03-23 18:57:05 ElKamina

给定有限的一组有序实数产生所有可能的子集，其总和<= k

回答

相关问题