Изменения
Нет описания правки
<tex>\langle j, mask - 2^j \rangle</tex>, и <tex>|mask| = |mask - 2^j| + 1</tex>, то состояния с большим <tex>|mask|</tex> должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта.
Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти).
//Все переменные используются из описания алгоритма, inf <tex>\infty</tex> = бесконечность
'''function''' findCheapest(i, mask):
'''if''' d[i][mask] != inf <tex>\infty</tex>
'''return''' d[i][mask]
'''for''' j = 0 .. n - 1
'''for''' i = 0 .. n - 1
'''for''' mask = 0 .. 2 ** n - 1
d[i][mask] = inf<tex>\infty</tex>
d[0][0] = 0;
ans = ''findCheapest'' (0, 2 ** n - 1)
if ans == inf<tex>\infty</tex>
exit
Дальше ищем сам путь:
