18
правок
Изменения
добавлена формулировка
==Формулировка задачи==
В '''Задаче о рюкзаке''' (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-полноты==
В '''Задаче о рюкзаке''' (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-полноты==
