Подмножество Sum TI Basic Programming

Question

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

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

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

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

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

так

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 внутри петель.

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

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

Answer 1

Для оптимизации вы просто хотите пропустить эти поддеревья поиска, где уже сейчас они превысят значение 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 разрешает использование более одного символа в имени переменной).

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