Как понять, что проблема с рюкзаком является NP-полной?

Question

Мы знаем, что проблема ранца может быть решена в O(nW) сложности с помощью динамического программирования. Но мы говорим, что это NP-полная проблема. Я чувствую, что это трудно понять здесь.

(n - количество предметов. W - максимальная громкость.)

Answer 1

O(n*W) выглядит как полиномиальное время, но это не так, это псевдополиномиальное.

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

Точнее говоря, временная сложность динамического решения задачи о ранце в основном определяется вложенным циклом:

// here goes other stuff we don't care about
for (i = 1 to n)
    for (j = 0 to W)
        // here goes other stuff

Таким образом, сложность времени явно O(n*W),

Что означает линейное увеличение размера входных данных алгоритма? Это означает использование более длинных массивов элементов (так n, n+1, n+2,...) и постепенно W (так что если W является x бит длиной, после одного шага мы используем x+1 биты, то x+2 биты, ...). Но ценность W растет в геометрической прогрессии с xТаким образом, алгоритм на самом деле не полиномиальный, он экспоненциальный (но, похоже, он полиномиальный, отсюда и название: "псевдополином").

---

Дальнейшие ссылки

• http://www.cs.ship.edu/~tbriggs/dynamic/index.html
• https://web.archive.org/web/20100627162045/http://websrv.cs.umt.edu/classes/cs531/index.php/Complexity_of_dynamic_programming_algorithm_for_the_0-1_knapsack_problem_3/27

Answer 2

В задаче о ранце 0/1 нам нужно 2 входа (1 массив и 1 целое число), чтобы решить эту проблему:

1. массив из n элементов: [n1, n2, n3, ... ], каждый элемент со своим индексом значения и индексом веса.
2. целое число W как максимально допустимый вес

---

Предположим, что n = 10 и W = 8:

1. n = [n1, n2, n3,..., n10]
2. W = 1000 в двоичном выражении (длина 4 бита)

поэтому сложность по времени T (n) = O (nW) = O (10 * 8) = O (80)

---

Если вы удвоите размер n:

n = [n1, n2, n3,..., n10] -> n = [n1, n2, n3,..., n20]

поэтому сложность по времени T(n) = O(nW) = O(20*8) = O(160)

---

но если вы удвоите размер W, это не значит, что W = 20, а длина в два раза больше:

W = 1000 -> W = 10000000 в двоичном выражении (8-битная длина)

поэтому T (n) = O (nW) = O (10 * 128) = O (1280)

необходимое время увеличивается в геометрической прогрессии, так что это проблема NPC.

Answer 3

Все зависит от того, какие параметры вы вводите внутри O(...),

Если целевой вес ограничен числом W, то проблема имеет O(n*W) сложность, как вы упомянули.

Но если вес слишком велик, и вам нужен алгоритм со сложностью, не зависящей от WТогда проблема NP-полна. (O(2^n*n) в самой наивной реализации).

Answer 4

Размер ввода log(W) биты для веса (и O(n) для массивов "value" и "weight").

Таким образом, входной размер веса j = log(W) (а не просто W). Так, W = 2ʲ (как бинарный используется).

Конечная сложность O(n * W)

это O(n * W) может быть переписан как O(n * 2ʲ), который экспоненциально по размеру входа.

Итак, это решение не является полиномиальным.

Answer 5

Это связано с тем, что задача о ранце имеет псевдополиномиальное решение и поэтому называется слабо NP-полной (а не сильно NP-полной).

Answer 6

Вы можете прочитать это краткое объяснение: NP-Полнота рюкзака.

Answer 7

Чтобы понять NP-полноту, вам нужно немного изучить теорию сложности. Тем не менее, в основном, он NP-завершен, потому что эффективный алгоритм для задачи о ранце также будет эффективным алгоритмом для SAT, TSP и всего остального.