将子集求和的近似算法转换为php代码

Question

Cross-posted in MathExchange to elicit more responses。

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

我在写我原来的问题在StackOverflow上，当我意识到它被问到before。

原来我有什么被称为一个子集和问题，让我去wikipedia，发现这部分。

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是一个列表。什么是S元素的列表0？

什么是if y + cs/N < z ≤ s？我怎样才能在代码中写出这些？

我希望有人可以帮我翻译成PHP代码这一点。

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

只要回答让我明白这个近似算法足以让我把它写在PHP代码自己，会做。

Answer 1

为了回答您发布的子问题上math.stackexchange.com一个接一个：

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

给定一组整数和整数小号，是否有任何非空子集总和小号？

但是是S，反正？粗略地说，S代表了集中的所有“有用”的款项，我们可以使用到目前为止，我们已经看到的元素（如果我没有记错的话）。

是否“与元素0的列表”是指含有单数，它是一个零的列表？是的，就是这个意思。

是什么y + cs/N < z ≤ s意思？这意味着y + c*s/N < z和z ≤ s。因此，只要y + c*s/N ≥ z或z > s（或两者）if将失败。

还有一些问题，你没有问，但似乎有可能上来：

什么是N？N是我们给出的集合中的元素数量。

什么是xi？xi是i我们给出的集合中的第 - 个元素。