C / C ++实现类似于子集和的算法

问题比knapsack （或其类型，没有值和只有正重量）更简单。 问题在于检查数字是否可以是其他数字的组合。 该函数应返回true或false 。

例如，

112和{ 17, 100, 101 }的列表应该返回false ， 469具有相同的列表应该返回true ， 35应该返回false ， 119应该返回true ，等等…

编辑：子集和问题比背包更准确。

Answer 1

一个可以帮助你的观察是，如果你的列表是{a，b，c …}并且你要测试的数字是x，那么只有当x或xa可以x时，x才可以写成子列表的总和写成子列表{b，c，…}的总和。 这使您可以编写一个非常简单的递归算法来解决问题。

编辑：这里有一些代码，考虑到下面的评论。 没有经过测试，可能是马车; 并不一定是最快的。 但是对于一个小型数据集，它可以整齐地完成工作。

 bool is_subset_sum(int x, std::list::const_iterator start, std::list::const_iterator end) { // for a 1-element list {a} we just need to test a|x if (start == end) return (x % *start == 0); // if x is small enough we don't need to bother testing x - a if (x 

Answer 2

这是子集和问题的特殊情况，其中集合仅包含一个负数（即，表示112和{17,100,101}为{-112,17,100,101}）。 维基百科页面上有一些算法， http：//en.wikipedia.org/wiki/Subset_sum_problem 。

Answer 3

请注意，随着查询数量变大，正结果会变得更密集。 例如，{17,100,101}可以生成大于100 ^ 2的所有数字。 因此，最优算法可能取决于查询的数量是否远大于集合的成员。 你可能会研究场论。

至少，如果集合的最大公约数不在查询中，并且可以在可忽略的时间内检查，则您知道结果始终为false。

Answer 4

如果要达到的数量不是太大，您可以生成集合中所有可达到的数字，这些数字落在[1，N]范围内。

问题：使用列表L的元素到达N ，其中N足够小，不用担心大小为N元素大小的向量。

算法：

• 生成大小为N的向量V
• 对于列表L中的每个元素l
  • 对于v中的每个可到达元素v
    • 将v + n*l所有元素v + n*l标记为可达