Уборка бина, решение против оптимизации

Question

Для задания мне была задана проблема с упаковкой в ​​корзине и попросил показать, как вы можете решить версию решения проблемы из версии оптимизации и наоборот. Я понимаю, что для решения версии решения вы просто берете количество ящиков, используемых в версии оптимизации, и сравниваете их с максимальным количеством указанных ящиков, но как я могу использовать версию решения для решения версии оптимизации?

Answer 1

Вы можете использовать версию решения для решения оптимизационной версии, заметив, что если достаточно N бункеров, то также будет достаточно K > N бункеров.

Начните с одного бункера и запустите на нем версию решения. Если ответ true, все готово; в противном случае, удвоение количества ящиков до тех пор, пока вы не нажмете true. Предположим, что вы получили ответ от true при попытке N = 2^k. Затем вы можете запустить двоичный поиск между M = 2^(k-1) и N, включительно, чтобы найти точное решение проблемы оптимизации (как N, так и k приведены на предыдущем шаге).

Рассмотрим следующий пример: допустим, оптимальное решение 14. Затем можно попробовать следующую последовательность задачи принятия решения, чтобы найти ответ:

• 1 ->false
• 2 ->false (удвоенный 1)
• 4 ->false (удвоенный 2)
• 8 ->false (удвоенный 4)
• 16 ->true (удваивается 8; мы получили true, поэтому переходим к бинарного поиска)
• 12 ->false (средняя точка между 8 и 16)
• 14 ->true (средняя точка между 12 и 16)
• 13 - >false (средняя точка между 12 и 14)

в общем, ответ может быть найден в логарифмической времени (т.е. Вход (ответ)).

После того, как вы знаете, количество бункеров N необходимых для упаковки X объектов, запустить двудольный алгоритм соответствия между элементами на одной стороне и N бункеров на другой стороне. Предполагая, что проблема решения решена правильно, должно существовать такое двудольное сопоставление, and can be found in polynomial time.