Целочисленный рюкзак и независимый набор (теория графов) Связанный?

Question

В ходе Алгоритмов-II по Тиму Роугардны на Coursera, объясняя проблему 0-1 рюкзака, он упоминает следующее, я цитирую

"По забирая Wn от емкости рюкзака, прежде чем мы рассмотрим остаточные подзадачи , мы фактически резервируем буфер для элемента N, если нам когда-либо понадобится его, и именно так мы знаем, что мы выполнимы, когда вернем N обратно в это решение S *. Это аналогично удалению предпоследней вершины пути, снова в качестве буфера для обеспечения выполнимости, когда мы включаем N-ю верхушку обратно в задание независимого набора ».

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

http://en.wikipedia.org/wiki/Independent_set_(graph_theory)

но не смог найти никакой связи между ними.

Answer 1

Как я понимаю этот фрагмент, автор пытается объяснить, как получить меньшую подзадачу из текущей проблемы.

В случае рюкзака, он означает, что, учитывая, например, весы {5, 3, 7, 1, 4} и ранец размера 15, вы можете создать подзадачу, выбрав первый пункт и, глядя на оставшемся месте. То есть оставшаяся проблема заключается в решении проблемы с рюкзаком для {3, 7, 1, 4} и размера рюкзака 10 (обратите внимание, что это только часть решения).

В автономном комплекте у вас есть нечто похожее. Учитывая вершины {A, B, C, D, E} и ребра {(A, B), (A, D), (B, C), (C, D), (C, E), (D, E)}, вы можете создать подзадачу, выбрав первую вершину (A) и посмотрите на оставшийся график. Все соседи A необходимо удалить, поэтому оставшаяся проблема состоит в том, чтобы найти независимый набор вершин {C, E} и ребра {(C, E)}.

Должен сказать, что это сходство довольно растянуто.