Subset Sum TI Basic Programming

Я пытаюсь запрограммировать свой TI-83 для поиска суммы подмножества. Итак, имея список длины N, я хочу найти все списки заданной длины L, сумма которых равна заданному значению V.

Это немного отличается от обычной проблемы суммы подмножества, потому что я ищу только подмножества заданной длины, а не все длины, и рекурсия не обязательно является первым выбором, потому что я не могу вызвать программу, в которой я работаю.

Я могу легко выполнить задачу с вложенными циклами, но это становится громоздким для значений L больше 5. Я пытаюсь найти динамические решения, но ничего не получаю.

На самом деле, на данный момент я просто пытаюсь сделать ссылки на список правильными, так что я смотрю именно на это. Давайте рассмотрим пример:

L1={p,q,r,s,t,u}

so

N=6

давайте искать все подмножества длины 3, чтобы сделать его относительно коротким, поэтому L = 3 (6c3 = 20 общих выходов).

В идеале ссылки списка, которые будут искаться, следующие:

{1,2,3}
{1,2,4}
{1,2,5}
{1,2,6}
{1,3,4}
{1,3,5}
{1,3,6}
{1,4,5}
{1,4,6}
{1,5,6}
{2,3,4}
{2,3,5}
{2,3,6}
{2,4,5}
{2,4,6}
{2,5,6}
{3,4,5}
{3,4,6}
{3,5,6}
{4,5,6}

Явно выполнено:

FOR A,1,N-2
    FOR B,A+1,N-1
        FOR C,B+1,N
            display {A,B,C}
        END
    END
END

Сначала я сортирую данные N по убыванию, что позволяет мне искать критерии, которые сокращают поиск, а использование циклов FOR немного портит его в разных местах, когда я увеличиваю значения A, B и C внутри циклов.

Я также ищу лучшие динамические решения. Я провел некоторое исследование в Интернете, но я не могу адаптировать то, что есть, к моей конкретной ситуации.

Любая помощь будет оценена по достоинству. Я стараюсь быть достаточно кратким, чтобы не писать роман, а объяснить, к чему я пытаюсь прийти. Я могу предоставить более подробную информацию по мере необходимости.


dynamic loops subset-sum ti-basic
person garrett    schedule 29.12.2009    source источник
comment
Я добавил тег ti-basic, потому что это язык программирования.. надеюсь, всем это нравится   -  person Earlz    schedule 29.12.2009
comment
Это нормально, @earlz, теперь мы вполне можем стать местом назначения для всех кодеров ti-basic :-) @Garrett, я также воспользовался возможностью, чтобы немного привести вопрос в порядок. Вы можете прочитать это, чтобы убедиться, что я ничего не напортачил.   -  person paxdiablo    schedule 29.12.2009
comment
Вы рассматривали возможные творческие способы использования gotos? или, возможно, используя 2 программы для реализации этого? (рекурсивно вызывая друг друга)   -  person Earlz    schedule 29.12.2009

Ответы (1)


arrow_upward
1
arrow_downward

Для оптимизации вы просто хотите пропустить те поддеревья поиска, где вы уже сейчас превысите значение V. Рекурсия — это путь, но, поскольку вы уже исключили это, вы будете лучше всего установить верхний предел допустимой глубины.

Я бы сделал что-то вроде этого (для глубины 3):

N is the total number of array elements.
L is the desired length (3).
V is the desired sum
Y[] is the array
Z is the total

Z = 0
IF Z <= V
  FOR A,1,N-L
    Z = Z + Y[A]
    IF Z <= V
      FOR B,A+1,N-L+1
        Z = Z + Y[B]
        IF Z <= V
          FOR C,B+1,N-L+2
            Z = Z + Y[C]
            IF Z = V
              DISPLAY {A,B,C}
            END
            Z = Z - Y[C]
          END
        END
        Z = Z - Y[B]
      END
    END
    Z = Z - Y[A]
  END
END

Теперь это довольно запутанно, но в основном проверяет на каждом этапе, превысили ли вы уже желаемое значение, и отказывается проверять нижние поддеревья в качестве меры эффективности. Он также сохраняет промежуточную сумму для текущего уровня, поэтому ему не нужно делать большое количество добавлений при проверке на более низких уровнях. Это сложение и вычитание значений массива против Z.

Это станет еще более сложным, когда вы измените его для обработки большей глубины (используя переменные от D до K для 11 уровней (больше, если вы хотите переместить N и L вниз до W и X). или если TI BASIC допускает более одного символа в имени переменной).

Единственный другой нерекурсивный способ, который я могу придумать, — это использовать массив групп значений для эмуляции рекурсии с итерацией, и это будет выглядеть лишь немного менее сложно (хотя код должен быть менее вложенным ).

person paxdiablo    schedule 29.12.2009