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

Ссылки сюда (2) →

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

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

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

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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.