子集总和-恢复解决方案 [英] Subset sum - Recover solution

问题描述

我编写了一种动态编程算法，该算法可以找到总计为目标值的子集总数.但是，我在开发用于恢复解决方案的功能时遇到了麻烦(即，打印出实际的子集).

I have written a dynamic programming algorithm that finds the total amount of subsets that sum up to a target value. However, I am having trouble developing a function to recover the solution (that is, print out the actual subsets).

例如，让我们将设置为 [1,3,5,7,9,10] 的目标为 13 .我的算法计算出有3个子集.输出表如下图所示.

For example, let's take the set [1,3,5,7,9,10] with the target 13. My algorithm calculates that there are 3 subsets. The output table is shown in the image below.

由于这是一个简单的集合，因此我可以手动确定组成目标的三个子集.那就是:

Because this is a simple set, I can manually determine which three subsets make up the target. That is:

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

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

But, with more complicated solutions, how would I use my output table to recursively recover a solution? Any assistance is appreciated.

推荐答案

注意事项

没有看到您的算法及其任何输入限制(例如，集合中是否允许重复值?)，可能无法设计出一种适用于所有可能情况的方法.

Caveat

Without seeing your algorithm and any input restrictions for it (for example, are duplicate values allowed in the set?) it might not be possible to devise a method that will work for all possible cases.

但是，对于您示例的结果表中列出的所有情况，以下内容似乎都适用.如果您发现这不适用于其他情况，请将这些示例添加到您的问题中.(在特殊情况下，我不考虑target = 0.)

It appears, however, that the following will work for all cases listed in the results table of your example. If you find that this does not work for other cases, please add those examples to your question. (I am disregarding target = 0 as a special case.)

以升序遍历目标列的结果.

Iterate through the results of the target column in ascending order.

结果递增时，您已识别出另一个子集并在该子集中找到了最大值.

When the result increments, you have identified another subset and have found the largest value in that subset.

要查找子集中的剩余值，请按照店员的方式进行更改".换句话说，退回设置值，并从剩余的总和中减去.

To find the remaining values in the subset, "make change" the way a store clerk would. In other words, walk back down the set values, subtracting from the remaining total as you can.

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

For your given example of target sum = 13 for subsets within set [1,3,5,7,9,10]:

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个子集:

End of run with 3 subsets identified:

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

这篇关于子集总和-恢复解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！