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

Question

这个问题比背包（或其一种类型，没有值，只有正权重）更简单。该问题包括检查一个数字是否可以是其他数字的组合。该函数应返回 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。

Answer 2

对您有帮助的观察是，如果您的列表是 {a, b, c...} 并且您要测试的数字是 x，则仅当 x 或 xa 可以时，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<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));
}

Answer 3

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

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

Answer 4

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

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

算法：

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