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

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

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

69 голосов | спросил cnhk 11 +04002010-10-11T19:17:57+04:00312010bEurope/MoscowMon, 11 Oct 2010 19:17:57 +0400 2010, 19:17:57

7 ответов


0

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, таким образом, алгоритм на самом деле не является полиномиальным, он экспоненциальный (но он выглядит как полиномиальный, отсюда и название: «псевдополином»).


Дополнительные ссылки

ответил Giuseppe Cardone 11 +04002010-10-11T19:57:03+04:00312010bEurope/MoscowMon, 11 Oct 2010 19:57:03 +0400 2010, 19:57:03
0

В задаче о ранце 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.

ответил YoEugene 31 WedEurope/Moscow2014-12-31T11:32:18+03:00Europe/Moscow12bEurope/MoscowWed, 31 Dec 2014 11:32:18 +0300 2014, 11:32:18
0

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

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

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

ответил Nikita Rybak 11 +04002010-10-11T19:23:08+04:00312010bEurope/MoscowMon, 11 Oct 2010 19:23:08 +0400 2010, 19:23:08
0

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

ответил Manav Kataria 31 J000000Wednesday13 2013, 01:55:48
0

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

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

Последняя сложность: O(n * W)

  

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

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

ответил kaushalpranav 31 Maypm16 2016, 16:30:17
0

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

ответил dfens 11 +04002010-10-11T19:47:34+04:00312010bEurope/MoscowMon, 11 Oct 2010 19:47:34 +0400 2010, 19:47:34
0

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

ответил Pontus Gagge 11 +04002010-10-11T19:25:38+04:00312010bEurope/MoscowMon, 11 Oct 2010 19:25:38 +0400 2010, 19:25:38

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132