1

在 MathExchange 中交叉发布以引起更多响应。

==================================================== ===============================

当我意识到之前有人问过这个问题时，我正在 StackOverflow 中写我最初的问题。

原来我有所谓的子集和问题，所以我去了维基百科并找到了这部分。

The algorithm for the approximate subset sum problem is as follows:
 initialize a list S to contain one element 0.
 for each i from 1 to N do
   let T be a list consisting of xi + y, for all y in S
   let U be the union of T and S
   sort U
   make S empty 
   let y be the smallest element of U 
   add y to S 
   for each element z of U in increasing order do
      //trim the list by eliminating numbers close to one another
      //and throw out elements greater than s
     if y + cs/N < z ≤ s, set y = z and add z to S 
 if S contains a number between (1 − c)s and s, output yes, otherwise no

但是我在理解维基百科中编写的伪代码时遇到了问题。

例如，我认为目标是找到可以匹配 S 的最接近的一组数字。

但这里 S 是一个列表。这个元素为 0 的 S 列表是什么？

到底是 if y + cs/N < z ≤ s什么？我什至如何用代码写出来？

我希望有人能帮我把它翻译成 php 代码。

至少我对此比较熟悉。它不必是完整的翻译。

只要答案让我足够理解这个近似算法，让我自己用 php 代码编写它，就可以了。

4

1 回答 1

3

要一一回答您在 math.stackexchange.com 上发布的子问题：

大S和 小 和有什么不一样s？bigS是一个列表变量，它最初是列表[0]，并在代码执行过程中被修改。小s是一个保持不变的数字。具体来说，s是这个问题的数字：

给定一组整数和一个整数s，是否有任何非空子集和s？

但是，到底是 S什么？粗略地说，S它代表了我们可以使用到目前为止所看到的元素得出的所有“有用”总和的集合（如果我没记错的话）。

“元素为 0 的列表”是否意味着包含单个数字的列表，该数字为零？是的，就是这个意思。

是什么y + cs/N < z ≤ s意思？这意味着y + c*s/N < z和z ≤ s。因此，无论何时或（或两者）if都会失败。y + c*s/N ≥ z z > s

还有一些你没有问过但似乎很可能会出现的问题：

是什么N？ N是给定集合中元素的数量。

是什么xi？ xi是给定集合的第i个元素。

于 2013-08-22T18:16:40.190 回答