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

Материал из DISCOPAL
< Жадный алгоритм в задачах о покрытии‎ | Задачи
Версия от 15:49, 20 мая 2020; StasFomin (обсуждение | вклад) (Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])

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


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

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

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

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

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

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

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

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