Почему решается ранцевый пробл. не рассматривается ли как линейное программирование?
Почему проблема рюкзака не входит в категорию алгоритмов линейного программирования , несмотря на то, что постановка задачи рюкзака похожа на задачи линейного программирования .?
1 ответ:
Ранец может быть записан как программа целочисленного линейного программирования. В отличие от обычного линейного программирования, эта задача требует, чтобы переменные в решении были целыми числами. Линейное программирование, как известно, разрешимо в полиномиальном времени, в то время как целочисленное линейное программирование является NP-полным.
Упражнение для читателя: покажите, что 3SAT можно свести к целочисленному линейному программированию.
Пустяки: существуют алгоритмы аппроксимации для таких задач, как MAX-3SAT (вариант 3SAT где мы хотим максимизировать число удовлетворяемых условий). Сначала вы пишете MAX-3SAT как целочисленную линейную программу. Затем вы расслабляете его до линейной программы, снимая целочисленное ограничение. Затем вы решаете линейную программу за полиномиальное время. Наконец, учитывая действительное x i ∈ [0,1], вы округляете их до целых чисел или генерируете случайное целочисленное решение y i , где вероятность y i = 1 равна x i.