Рюкзак с взаимоисключающими изделиями

Question

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

Оригинальная задача о рюкзаке является то, что данный ранец с размером W и список предметов, вес которых w[i] и имеет значение v[i], найти подмножество предметов, которые могут поместиться в рюкзаке с самой высокой общей стоимостью.

Для меня это может быть сделано O(Wn) с динамическим программированием, где n - это количество элементов.

---

Теперь, если я пытаюсь добавить m Сдерживает, каждый из них является пара элементов, которые могут быть выбраны только взаимное исключительно (т.е. если существует Ограничить из пункта А и пункт Б, то я могу взять только либо один из них, но не оба)

При таких ограничениях эта проблема может быть решена путем динамического программирования в O(Wn)?

Answer 1

Успение: Каждый элемент включен в крайнее ограничение.

Для обычной задачи о рюкзаке, оптимальная подструктура, что задача обладает следующим образом:

Для каждого элемента могут быть два случая:
1. Пункт включен в растворе
2. элемент, не включенный в решение.

Следовательно, оптимальное решение для пунктов n задается макс. Следующих двух значений.
1. Максимальное значение получено по n-1 предметам и W веса.
2. v_n + максимальное значение получено n-1 изделиями и W-w_n масса.

Теперь, если мы добавим ограничение, что в решении может существовать любой из n th или (n-1)-го элемента, тогда оптимальное решение для элементов n задается максимальным количеством следующих трех значений.
1. Максимальное значение, полученное по n-2 предметам и W Масса.
2. v_n + максимальное значение получено n-2 и W-w_n масса.
3. v_(n-1) + максимальное значение получено n-2 и W-w_(n-1) масса.

Поэтому мы рассматриваем каждую пару элементов в ограничении как один элемент и выполняем алгоритм динамического программирования в O(Wn) времени.