algorithm - 给定一组 n 个整数，列出所有可能的子集，其中 k1<= sum <=k2 ， k1 和 k2 浮点数

Question

给定一个数组形式的未排序整数集，找到所有可能的子集，其总和大于 k1 且小于 k2 ，其中 k1 ,k2 是两个浮动常量，例如：- 我们的集合是 {2,3,5,8 ,10} 和 k1 =10 和 k2 = 12。

可能的子集：-

{2,3,5}
{8,2}
{8,3}
{10}
{10,2}

我只能想到一个幼稚的算法，有没有更好的方法或类似的问题，请给一些建议。它实际上是我项目工作的重要组成部分？有没有可用的动态规划方法？

标签： algorithmdynamic-programmingsubset-sum

Answer 1

是的，动态规划方法确实存在。
制作长度为 k2+1 的表（列表数组）并填充它：
对于从末尾到开头的每个值V=A[i]扫描数组，并添加V到单元格中的列表中j-th，如果Table[j - V]不为空（因此我们可以将值j添加V到从Table[j - V]）
最后检查具有所需总和的单元格并恢复序列。

2,3,5 的示例：

 0    1    2   3   4   5   6   7   8   9   10    //index
 [0]                                             //initial state
 [0]      [2]                                    //after 2   
 [0]      [2]  [3]    [3]                        //after 3     
 [0]      [2]  [3]    [3,5]   [5] [5]      [5]   //after 5

要检索总和 5 的集合 - 到达第五个单元格并将值展开到左侧。 3表示我们去5-3=2，然后使用2 直到零条目。第二种变体 -5我们进入零条目。所以值 5 可能是从 set{5}或从 set产生的{3,2}

请注意，存储序列数据可能需要大量空间，而恢复序列可能需要2^N时间——当有很多好的子集时。