NP-полнота задачи о рюкзаке — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(добавлена формулировка)
 
(Доказательство закончено)
Строка 1: Строка 1:
 
==Формулировка задачи==
 
==Формулировка задачи==
−
В '''Задаче о рюкзаке''' (Knapsack problem) входными данными являются набор <math>n</math> пар целых чисел <math>w_{i}</math> - вес и <math>v_{i}</math> - стоимость, а также два целых числа <math>c</math> - максимальный вес и <math>p</math> - минимальная стоимость. Требуется определить, можно ли выбрать такое подмножество пар, что их суммарная стоимость больше либо равна <math>p</math>, а вес меньше или равен <math>c</math>:
+
В '''Задаче о рюкзаке''' (Knapsack problem) входными данными являются набор <math>n</math> пар целых чисел <math>\{w_{i}\}</math> - вес и <math>\{v_{i}\}</math> - стоимость, а также два целых числа <math>c</math> - максимальный вес и <math>p</math> - минимальная стоимость. Требуется определить, можно ли выбрать такое подмножество пар, что их суммарная стоимость больше либо равна <math>p</math>, а вес меньше или равен <math>c</math>:
  
 +
<p style="text-align:center;">
 
<math>\exist \{k_{j}\} \subseteq (1..n): (\sum_{i \in k_{j}}{v_{i}} \geq p) \wedge (\sum_{i \in k_{j}}{w_{i}} \leq c)</math>
 
<math>\exist \{k_{j}\} \subseteq (1..n): (\sum_{i \in k_{j}}{v_{i}} \geq p) \wedge (\sum_{i \in k_{j}}{w_{i}} \leq c)</math>
 +
</p>
 
==Доказательство NP-полноты==
 
==Доказательство NP-полноты==
 +
Для доказательства того, что <math>Knapsack~ problem \in NPC</math> необходимо доказать два факта:
 +
*<math>Knapsack~ problem \in</math> [[NP|<math>NP</math>]]
 +
*<math>Knapsack~ problem \in</math> [[NPH|<math>NPH</math>]]
 +
===Доказательство принадлежности к NP===
 +
В качестве сертификата возьмем удовлетворяющее условию задачи подмножество пар <math>\{k_{j}\}</math>. Очевидно, оно удовлетворяет всем требованиям,
 +
налагаемым на сертификат.
 +
===Доказательство принадлежности к NPH===
 +
Сведем [[NP-полнота задачи о сумме подмножества|задачу о сумме подмножества]] к задаче о рюкзаке. Пусть <math>f\!\!:(\{s_{i}\},s) \to (\{w_{i}\},\{v_{i}\},c,p)</math> - функция, осуществляющее сведение. Она будет устроена так: 
 +
 +
<p style="text-align:center;">
 +
<math>f(\{s_{i}\},s) = (\{s_{i}\},\{s_{i}\},s,s)</math>
 +
</p>
 +
Очевидно, <math>f</math> работает за полиномиальное от длины входа время. И удовлетворяет условиям [[Сводимость по Карпу|сводимости по Карпу]].

Версия 23:19, 8 марта 2010

Формулировка задачи

В Задаче о рюкзаке (Knapsack problem) входными данными являются набор [math]n[/math] пар целых чисел [math]\{w_{i}\}[/math] - вес и [math]\{v_{i}\}[/math] - стоимость, а также два целых числа [math]c[/math] - максимальный вес и [math]p[/math] - минимальная стоимость. Требуется определить, можно ли выбрать такое подмножество пар, что их суммарная стоимость больше либо равна [math]p[/math], а вес меньше или равен [math]c[/math]:

[math]\exist \{k_{j}\} \subseteq (1..n): (\sum_{i \in k_{j}}{v_{i}} \geq p) \wedge (\sum_{i \in k_{j}}{w_{i}} \leq c)[/math]

Доказательство NP-полноты

Для доказательства того, что [math]Knapsack~ problem \in NPC[/math] необходимо доказать два факта:

Доказательство принадлежности к NP

В качестве сертификата возьмем удовлетворяющее условию задачи подмножество пар [math]\{k_{j}\}[/math]. Очевидно, оно удовлетворяет всем требованиям, налагаемым на сертификат.

Доказательство принадлежности к NPH

Сведем задачу о сумме подмножества к задаче о рюкзаке. Пусть [math]f\!\!:(\{s_{i}\},s) \to (\{w_{i}\},\{v_{i}\},c,p)[/math] - функция, осуществляющее сведение. Она будет устроена так:

[math]f(\{s_{i}\},s) = (\{s_{i}\},\{s_{i}\},s,s)[/math]

Очевидно, [math]f[/math] работает за полиномиальное от длины входа время. И удовлетворяет условиям сводимости по Карпу.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=NP-полнота_задачи_о_рюкзаке&oldid=40»