c++ - 一个类似于子集求和的算法的C/C++实现

Question

这个问题比knapsack(或者它的一种类型，没有值，只有正权重)简单。该问题包括检查一个数字是否可以是其他数字的组合。该函数应返回 true 或 false。

例如，

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

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

Answer 1

这是子集和问题的一个特例，集合只包含一个负数(即，将 112 和 { 17, 100, 101 } 表示为 { -112, 17, 100, 101 })。维基百科页面上有一些算法，http://en.wikipedia.org/wiki/Subset_sum_problem .