Как понять, что проблема с рюкзаком является 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
• 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. целое число Ш как максимально допустимый вес

---

Давайтепредположим, что 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 = 16, но длина будет вдвое больше:

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

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

Answer 5

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

Итак, входной размер веса равен j = log(W) (а не просто W). Итак, W = 2ʲ (в качестве бинарного файла).

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

Этот O(n * W) можно переписать как O(n * 2ʲ), что экспоненциально по отношению к размеру ввода.

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

Answer 6

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

Answer 7

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