Жадный алгоритм в задачах о покрытии/Задачи/bin packing problem-maximize — различия между версиями

Версия 14:39, 8 декабря 2017

Рассмотрим Bin Packing Problem и модификацию этой задачи — пусть у нас можно потратить эти самые m контейнеров объема V, нет задачи упаковать все предметы, но надо постараться максимизировать число упакованных предметов.

И пусть суммарный вес всех n предметов не больше M*V.

Рассмотрим простой последовательный алгоритм для этого, типа first fit.

• Берем предметы в исходном порядке
• Пытаемся упаковать каждый в первый попавшийся контейнер, в который он лезет.
• Если не лезет ни в один из m, контейнеров, выкидываем этот предмет.

Докажите, что этот алгоритм упакует как минимум n/2 предметов.