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

Материал из DISCOPAL
Перейти к: навигация, поиск


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

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

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

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

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