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.
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.