Примеры счетчиков для задачи о ранце 0-1 с двумя ранцами - PullRequest
Новая
       49

Примеры счетчиков для задачи о ранце 0-1 с двумя ранцами

0 голосов
/ 25 декабря 2018

Я наткнулся на следующий вопрос в этом курсе:

Рассмотрим вариант задачи о рюкзаке, когда у нас есть два рюкзака с целочисленными емкостями ?1 и ?2.Как обычно, нам дается ? элементов с положительными значениями и целыми положительными весами.Мы хотим выбрать подмножества ?1, ?2 с максимальным общим значением таким образом, чтобы суммарные веса ?1 и ?1 были не более most1 и ?2 соответственно.Предположим, что каждый предмет помещается в любой рюкзак.Рассмотрим следующие два алгоритмических подхода.

(1) Используйте алгоритм из лекции, чтобы выбрать максимально допустимое решение ?1 для первого ранца, а затем снова запустите его на оставшихся предметах, чтобы выбрать максимальное значениевыполнимое решение ?2 для второго рюкзака.

(2) Используйте алгоритм из лекции, чтобы выбрать максимально возможное решение для рюкзака с емкостью ?1 + ?2, а затем разбейте выбранные элементы на два набора ?1 +?2 имеют размер не более ?1 и ?2 соответственно.

Какое из следующих утверждений верно?

  1. Алгоритм (1) гарантированно даст оптимальное выполнимое решениек исходной задаче при условии =1 = ?2.

  2. Алгоритм (1) гарантированно даст оптимальное выполнимое решение исходной задачи, а алгоритм (2) - нет.

  3. Алгоритм (2) гарантированно даст оптимальное выполнимое решение исходной задачи, а алгоритм (1) - нет.

  4. Не гарантируется, что ни один алгоритм даст оптимальное реальное решение исходной задачи.

«Алгоритм из лекции» включенYouTube.https://www.youtube.com/watch?v=KX_6OF8X6HQ,, что является проблемой ранца 0-1 для одной сумки.

Правильный ответ на этот вопрос - вариант 4. Это , , это и этот пост представить решения проблемы.Однако мне трудно найти контрпримеры, показывающие, что варианты с 1 по 3 неверны.Можете ли вы привести что-нибудь еще?

Редактировать: Принятый ответ не дает контрпример для варианта 1;см. 2 рюкзака с одинаковой вместимостью - почему мы не можем просто найти максимальное значение дважды для этого.

1 Ответ

0 голосов
/ 25 декабря 2018

(Weight; Value): (3;10), (3;10), (4;2) вместимость 7, 3

Первый метод выбирает 3 + 3 в первый мешок, остальные предметы не помещаются во второй

(Weight; Value): (4;10), (4;10), (4;10), (2:1) вместимость 6, 6

Второй метод выбирает (4 + 4 + 4), но этот набор не может поместиться в два мешка без потерь, в то время как (4 + 2) и (4) лучше

...