translate approximate algorithm for subset sum into php code

Question

Cross-posted in MathExchange to elicit more responses.

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

I was writing my original question in StackOverflow, when I realized it was asked before.

Turns out I have what is known as a subset sum problem, so I went to wikipedia and found this part.

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

But I have problem understanding the pseudo code written in wikipedia.

For instance, I thought the objective is to find the closest set of numbers that can match S.

But here S is a list. What is this S list with element 0?

And what on earth is if y + cs/N < z ≤ s? How do I even write this out in code?

I was hoping someone can help me translate this into php code.

At least I am more familiar with that. It need not be a full translation.

As long as the answers make me understand this approximate algorithm enough for me to write it in php code myself, that will do.

Answer 1

To answer the sub-questions you posted on math.stackexchange.com one by one:

What is the difference between the big S and the small s? The big S is a list variable which is initially the list [0] and is modified over the course of the execution of the code. The little s is a number that remains constant. Specifically, s is the number from this question:

Given a set of integers and an integer s, does any non-empty subset sum to s?

But what is S, anyway? Roughly speaking, S represents the set of all "useful" sums that we can make using the elements we've seen so far (if I'm not mistaken).

Does "a list with element 0" mean a list containing a single number, which is zero? Yes, that's what that means.

What does y + cs/N < z ≤ s mean? It means that y + c*s/N < z and z ≤ s. So the if will fail whenever y + c*s/N ≥ z or z > s (or both).

And some questions you didn't ask, but which seem likely to come up:

What is N? N is the number of elements in the set we are given.

What is xi? xi is the i-th element of the set we are given.