4
2

Я имею ввиду NP-полную задачу. У нее имеются множество вариаций, мне интересна эта. У меня пара вопросов:

1) (именно по той вариации задачи) Нужно выбрать несколько предметов так, чтобы их суммарных вес был меньше или равен $%W$% (15 кг. на той картинке), или он должен быть точно равен $%W$%, и при этом у этих вещей была бы максимальная стоимость?

2)Понятно, что перебирая все варианты мы рассматриваем каждый предмет, но, допустим, есть алгоритм, по которому все варианты перебирать не нужно, а нужно просто рассмотреть каждый предмет, а дальше уже можно будет все определить. Будет ли такой алгоритм эффективным? То есть это и есть цель задачи?

задан 28 Мар '14 19:06

изменен 28 Мар '14 19:07

1

В задаче о рюкзаке можно рассматривать и то, и другое условие. Одно легко сводится к другому. Из соображений практики кажется более разумным условие $%\le P$%, но при теоретическом рассмотрении задачи, случай равенства представляется более удобным.

Поскольку про "обходные" алгоритмы вообще не известно, есть ли они, то спрашивать, эффективны ли они, можно только после того, как некий конкретный алгоритм предъявлен. Он должен работать не слишком долго, и при этом быть правильным. Априори неизвестно, как он мог бы выглядеть -- в этом и состоит основная проблема.

(28 Мар '14 20:07) falcao
1

Вот ещё пояснение на всякий случай. Пусть имеется граф с n вершинами. Мы хотим его вершины раскрасить в два цвета. При этом соседние вершины (соединённые ребром) должны иметь разные цвета. Это не всегда возможно. При полном переборе мы бы стали рассматривать все $%2^n$% способов раскраски вершин. Это очень много. Но есть "обходной" алгоритм, который работает быстро. Окрашиваем одну вершину в цвет 1, соседние с ней -- в цвет 2, соседние с ней (из не окрашенных) -- снова в цвет 1, и так далее. Получится либо искомая раскраска, либо противоречие. А для трёх цветов эта задача уже будет NP-полна.

(28 Мар '14 20:12) falcao

@falcao: спасибо за пояснение. Как я понял, во втором примере Вы говорили про хроматическое число. Чуть позже я пришлю Вам еще один вопрос (если можно его назвать вопросом) на почту (так будет удобнее).

(28 Мар '14 20:41) kirill1771

Да, эта задача связана с вопросом о том, каково хроматическое число графа. Но в данном случае имеется в виду частный случай, когда это число не превосходит 2 или 3.

На почту -- да, пишите!

(28 Мар '14 20:50) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,926

задан
28 Мар '14 19:06

показан
518 раз

обновлен
28 Мар '14 20:50

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru