NP-полнота задачи о рюкзаке — различия между версиями
Miron (обсуждение | вклад) (Доказательство закончено) |
|||
| (не показано 6 промежуточных версий 3 участников) | |||
| Строка 1: | Строка 1: | ||
==Формулировка задачи== | ==Формулировка задачи== | ||
| − | В ''' | + | В '''задаче о рюкзаке''' (Knapsack problem) входными данными являются набор <math>n</math> пар целых чисел <math>P = \{(w_{i},v_{i})\}^{n}_{i=1}</math>, где <math>w_{i}</math> - вес i-го предмета, а <math>v_{i}</math> - стоимость, и также два целых числа <math>c</math> - максимальный вес и <math>p</math> - минимальная стоимость. Требуется определить, можно ли выбрать такой набор предметов, что их суммарная стоимость больше либо равна <math>p</math>, а вес меньше или равен <math>c</math>: |
<p style="text-align:center;"> | <p style="text-align:center;"> | ||
| − | <math>\ | + | <math>\exists P' \subseteq P: ((\sum_{(w_{i},v_{i}) \in P'}{v_{i}} \geq p) \wedge (\sum_{(w_{i},v_{i}) \in P'}{w_{i}} \leq c))</math> |
</p> | </p> | ||
| + | |||
==Доказательство NP-полноты== | ==Доказательство NP-полноты== | ||
| − | Для доказательства того, что <math> | + | Для доказательства того, что Knapsack problem <math>\in</math> [[NPC]], необходимо доказать два факта: |
| − | *<math> | + | *Knapsack problem <math>\in</math> [[NP]] |
| − | *<math> | + | *Knapsack problem <math>\in</math> [[NPH]] |
===Доказательство принадлежности к NP=== | ===Доказательство принадлежности к NP=== | ||
| − | В качестве сертификата возьмем удовлетворяющее условию задачи подмножество пар <math> | + | В качестве сертификата возьмем удовлетворяющее условию задачи подмножество пар <math>P'</math> с суммарным весом, не большим <math>c</math> и стоимостью не меньше <math>p</math>. Очевидно, оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом и работает за полиномиальное от размера входа время. |
| − | налагаемым на сертификат. | ||
===Доказательство принадлежности к NPH=== | ===Доказательство принадлежности к NPH=== | ||
| − | Сведем [[NP-полнота задачи о сумме подмножества|задачу о сумме подмножества]] к задаче о рюкзаке. Пусть <math>f\!\!:( | + | Сведем [[NP-полнота задачи о сумме подмножества|задачу о сумме подмножества]] к задаче о рюкзаке. Пусть <math>f\!\!:(S,s) \to (P,c,p)</math> - функция, осуществляющее сведение. Она будет устроена так: |
<p style="text-align:center;"> | <p style="text-align:center;"> | ||
| − | <math>f( | + | <math>f(S,s) = ((S,S),s,s)</math>, |
</p> | </p> | ||
| − | Очевидно, <math>f</math> работает за полиномиальное от длины входа время. | + | То есть, для каждого числа <math>q \in S</math> создадим предмет <math>(q,q)</math> с весом и стоимостью, равными значению числа <math>q</math>. |
| + | А значения <math>c</math> и <math>p</math> возьмем равными <math>s</math>. | ||
| + | *Очевидно, <math>f~</math> работает за полиномиальное от длины входа время. | ||
| + | *Если исходная [[NP-полнота задачи о сумме подмножества|задача о сумме подмножества]] имела решение <math>S'</math>, то набор пар <math>P'</math> с весами, равными числам из <math>S'</math>, будет решением задачи о рюкзаке. | ||
| + | *В обратную сторону - аналогично. | ||
| + | |||
| + | [[Категория:NP]] | ||
Версия 01:04, 11 октября 2019
Содержание
Формулировка задачи
В задаче о рюкзаке (Knapsack problem) входными данными являются набор пар целых чисел , где - вес i-го предмета, а - стоимость, и также два целых числа - максимальный вес и - минимальная стоимость. Требуется определить, можно ли выбрать такой набор предметов, что их суммарная стоимость больше либо равна , а вес меньше или равен :
Доказательство NP-полноты
Для доказательства того, что Knapsack problem NPC, необходимо доказать два факта:
Доказательство принадлежности к NP
В качестве сертификата возьмем удовлетворяющее условию задачи подмножество пар с суммарным весом, не большим и стоимостью не меньше . Очевидно, оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом и работает за полиномиальное от размера входа время.
Доказательство принадлежности к NPH
Сведем задачу о сумме подмножества к задаче о рюкзаке. Пусть - функция, осуществляющее сведение. Она будет устроена так:
,
То есть, для каждого числа создадим предмет с весом и стоимостью, равными значению числа . А значения и возьмем равными .
- Очевидно, работает за полиномиальное от длины входа время.
- Если исходная задача о сумме подмножества имела решение , то набор пар с весами, равными числам из , будет решением задачи о рюкзаке.
- В обратную сторону - аналогично.
