Динамическое программирование - круговой максимально взвешенный независимый набор

Question

Я понимаю алгоритм MWIS с его подзадачей

A [i] = max (A [i-1], A [i-2] + W [i])

как эта реализация

Но когда он добавляет условие о том, чтобы сделать последовательность круговой, означает, что 1-й элемент подключен к последнему узлу.

Я застрял и не смогне разобраться в правильных подзадачах ..

Answer 1

Ответ на самом деле довольно прост. Предположим, у вас есть список весов узлов из A, где A[i] подключен к A[i-1] и A[i+1].

Также предположим, что у вас есть функция solve(), которая решает проблему MWIS, когда первый и последний узлы не подключены .

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

Следовательно, ответ - это максимум максимум solve(A[1:]) (решение для массива без первого узла) и solve(A[:-1])(решение для массива без последнего узла).

Почему это правильно? Рассмотрим оптимальный ответ. Он должен отсутствовать либо A[0], либо A[-1], поэтому он должен быть подмножеством A[1:] или A[:-1].

.