子集问题 - 任何材料？

Question

是的，这是一项家庭作业/实验作业。 我很感兴趣提出/发现一个算法（我可以理解：P）使用“回溯”来解决子集求和问题。

任何人都有一些有用的资源？我花了最后一个小时左右的时间用Google搜索，并不像找到我认为可以实际使用的东西。 xD

谢谢！

Answer 1

将数据放入向量中。

然后编写一个包含3个参数的例程：矢量，索引和和。 调用这个例程使用以下参数：向量，0，0。

的例程应执行以下任务：

• 检查，如果我们达到了向量（指数==大小）结束。如果是这样，我们可以立即返回。
• 呼叫本身与参数：矢量，索引+ 1，总和+矢量[指数] （在这种情况下，我们的索引处添加的元素的总和，并继续用该载体）
• 呼叫本身与参数：矢量，

我特意在这种算法忽略了2份指数+ 1，总和 （在这种情况下，我们没有索引的总和，在添加的元素，但仍然继续）：

• 首先，您应该在某个时候检查总和。如果它是零，那么你发现了一个正确的子集秒，你应该也传递关于你使用哪些元素的知识，所以如果和为零，你可以打印出子集。考虑为此使用STL :: set。

或者，您可以使用该函数的返回值来确定是否已找到正确的子集。

该算法的复杂性是O（2^N），所以对于大集合它会很慢。

玩得开心。