2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Задача о рюкзаке NP-трудна
Сообщение26.10.2013, 15:31 


02/11/11
124
Задача о рюкзаке рассматривается в такой формулировке: максимизировать $\sum c_j x_j$ по целым $x_j$ при условии $\sum w_jx_j \leqslant K$ (суммы от 1 до $n$).

Задача является NP-трудной, ну то есть если бы для нее существовал полиномиальный алгоритм, то существовал бы для любой задачи из NP.

Обычно NP-трудность некоторой задачи $A$ доказывают построением полиномиального алгоритма для какой-нибудь NP-полной задачи в предположении существования полиномиального алгоритма для $A.$ Как быть с задаче о рюкзаке в этом случае?

Обычно рассматривается целочисленный рюкзак (существуют ли целые $x_j$, такие что $\sum c_j x_j = K;$ $c_j, K$ -- целые) и 0-1 рюкзак (так же, но $x_j \in \{0,1\}$). Свести к этим задачам как-то не получается, как же быть?

Где, быть может, можно прочитать, конкретно об NP-трудности именно этой задачи?

 Профиль  
                  
 
 Re: Задача о рюкзаке NP-трудна
Сообщение26.10.2013, 16:33 


23/12/07
1757
Как-то намешано в вопросе все в кучу... Какую именно задачу к какой хотелось бы свести?
- "максимизировать" к "существует ли"
- "произвольные коэффициенты $w_j$" к "целым $c_j$"
- "$= K$ " к "$\leqslant K$"
?

По поводу литературы, возможно, имеет смысл глянуть "Босс В. Лекции по математике т.10 Перебор и эффективные алгоритмы "

 Профиль  
                  
 
 Re: Задача о рюкзаке NP-трудна
Сообщение26.10.2013, 18:12 


02/11/11
124
Ну почему же в кучу...
Вопрос - как доказать NP-трудность задаче о рюкзаке в общей (приведенной в начале первого сообщения) формулировке?

При этом есть знания о том, что задачи о целочисленном рюкзаке и о 0-1 рюкзаке NP-полны как задачи распознавания. Если это не поможет, надо что-то еще...

 Профиль  
                  
 
 Re: Задача о рюкзаке NP-трудна
Сообщение26.10.2013, 22:18 


23/12/07
1757
Может, я чего не понимаю, но в чем тогда проблема? Считаем, что ваша задача
max(Im) в сообщении #780441 писал(а):
максимизировать $\sum c_j x_j$ по целым $x_j$ при условии $\sum w_jx_j \leqslant K$ (суммы от 1 до $n$)

полиномиально разрешима. Тогда, рассматривая ее частный случай $w_j = c_j$, получаем полиномиальную разрешимость задачи
$$\sum c_i x_i \rightarrow \max, \quad  \sum c_i x_i \leqslant K, $$
применяя которую, легко решить задачу распознавания существования решения уравнения $\sum c_i x_i = K$ (для этого достаточно сравнить найденный максимум с числом $K$). Ну, а это будет означать полиномиальную разрешимость задачи распознавания для рюкзака, как вы и хотели
max(Im) в сообщении #780441 писал(а):
Обычно NP-трудность некоторой задачи $A$ доказывают построением полиномиального алгоритма для какой-нибудь NP-полной задачи в предположении существования полиномиального алгоритма для $A.$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group