перевод приблизительного алгоритма для суммы подмножества в код 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?

Но что является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 является -м элементом множества нам дано я.