子集和 - 恢复解决方案

Question

我编写了一个动态规划算法，用于查找总和为目标值的子集总数。但是，我在开发恢复解决方案的功能（即打印出实际子集）时遇到了问题。

例如，我们以目标 13 的集合 [1,3,5,7,9,10] 为例。我的算法计算出有 3 个子集。输出 table 如下图所示。

因为这是一个简单的集合，我可以手动确定目标是由哪三个子集组成的。即：

[3,10]
[1,3,9]
[1,5,7]

但是，对于更复杂的解决方案，我将如何使用我的输出 table 递归地恢复解决方案？任何帮助表示赞赏。

Answer 1

警告

如果没有看到您的算法及其任何输入限制（例如，集合中是否允许重复值？），可能无法设计出适用于所有可能情况的方法。

但是，以下内容似乎适用于示例结果 table 中列出的所有情况。如果您发现这不适用于其他情况，请将这些示例添加到您的问题中。（我忽略了 target = 0 作为特例。）

算法草图

按升序遍历目标列的结果。

当结果递增时，您已经确定了另一个子集并找到了该子集中的最大值。

要查找子集中的剩余值，"make change" 就像店员那样。换句话说，沿着设定值往回走，尽可能地从剩余总数中减去。

样本运行

对于集合 [1,3,5,7,9,10] 中子集的目标总和 = 13 的给定示例：

resultCount = 0

result(13,1) is 0; this result - resultCount = 0, so no new subsets

result(13,3) is 0; this result - resultCount = 0, so no new subsets

result(13,5) is 0; this result - resultCount = 0, so no new subsets

result(13,7) is 1; this result - resultCount = 1, so resultCount = 1
                                                     and new subset = [7]
                                                     and remaining = 13 - 7 = 6
    5 < 6, so subset = [7,5] and remaining = 6 - 5 = 1
    3 > 1, so remaining is still 1
    1 = 1, so subset = [7,5,1] and remaining = 0 (subset complete)

result(13,9) is 2; this result - resultCount = 1, so resultCount = 2
                                                     and new subset = [9]
                                                     and remaining = 13 - 9 = 4
    7 > 4, so remaining is still 4
    5 > 4, so remaining is still 4
    3 < 4, so subset = [9,3] and remaining = 4 - 3 = 1
    1 = 1, so subset = [9,3,1] and remaining = 1 - 1 = 0 (subset complete)

result(13,10) is 3; this result - resultCount = 1, so resultCount = 3
                                                      and new subset = [10]
                                                      and remaining = 13 - 10 = 3
    9 > 3, so remaining is still 3
    7 > 3, so remaining is still 3
    5 > 3, so remaining is still 3
    3 = 3, so subset = [10,3] and remaining = 3 - 3 = 0 (subset complete)

运行结束，识别出 3 个子集：

[7,5,1]
[9,3,1]
[10,3]

子集和 - 恢复解决方案

Subset sum - Recover solution

algorithm

sum

dynamic

subset

recover

警告

算法草图

样本运行