Рюкзак с предметами для учета ограничений

Question

У меня есть предметы I1, I2, I3, I4 с весами W1 ... W4 и значениями V1 ... V4.Я хочу максимизировать значения с минимальными весами.Это традиционный рюкзак.Однако есть небольшие ограничения, некоторые элементы не могут идти вместе.Допустим, I2 и I3 не могут идти вместе.Может ли кто-нибудь предоставить решение для динамического программирования или любое другое решение для того же.

Answer 1

С этим ограничением проблема становится сильно (в отличие от дискретного ранца, который только слабо NP-сложен), NP-сложна. Предположим, что все ваши вещи имеют вес 1 и значение 1.

Решение о том, можете ли вы получить значение k (при условии, что вместимость ранца> = k ) эквивалентно обнаружению k элементов, между которыми нет ограничений. Это известная NP-сложная проблема: независимый набор .

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