0

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

例如，

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

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

4

4 回答 4

3

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

于 2010-01-28T08:08:25.050 回答
2

一个对您有帮助的观察是，如果您的列表是 {a, b, c...} 并且您要测试的数字是 x，那么只有当 x 或 xa 可以写为子列表 {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<a) return is_subset_sum (x, start+1, end);

  // the default case. Note that the shortcut properties of || means the process ends as soon as we get a positive.
  return (is_subset_sum (x, start+1, end) || is_subset_sum (x-a, start, end));
}
于 2010-01-28T08:04:49.553 回答
2

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

至少，如果集合的最大公约数不在查询中，您知道结果总是错误的，并且可以在可忽略不计的时间内进行检查。

于 2010-01-28T08:30:21.507 回答
1

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

问题：N使用 list 中的元素到达L， whereN足够小，不必担心 sizeN元素大小的向量。

算法：

  • 生成一个V大小的向量N
  • l对于列表中的每个元素L
    • v对于每个可达元素V
      • v + n*l将V 中的所有元素标记为可访问
于 2010-01-28T08:42:05.330 回答