给定一组 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}

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

Answer 1

是的，动态规划方法确实存在。
制作长度为 k2+1 的 table（列表数组）并填充它：
对于每个值 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 可以从集合 {5} 或集合 {3,2}

中产生

请注意，存储序列数据可能需要很多 space，恢复序列可能需要多达 2^N 时间 - 当有很多好的子集时。

Answer 2

是的，实际上可以通过以下方式解决： subset sum problem

由于该集合包含所有整数，因此您只需键入将 K1 和 K2 强制转换为整数，然后检查哪些子集属于给定范围。

DP[N][sum_of_all_elements];

现在你得到了集合中的一个元素，比如 DP[N-1][x]，即K1<=x<=K2.

现在您需要在 DP[][] 数组中向上移动以找到集合中的下一个元素，因此 on.And 您需要对每个具有值的子集执行此操作(K1<=值 <=K2)

Answer 3

将此问题减少到 F(k1,k2) = F'(k1)+F'(k1+1)+...+F'(K2)。

那么F'(k)就是一个简单的DP解

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

Given a set of n integers, list all possible subsets with k1<= sum <=k2 , k1 and k2 floating numbers

algorithm

dynamic-programming

subset-sum