Жадный алгоритм в задачах о покрытии/Задачи/fist-fit-for-vector-packing

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

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Рассмотрим многомерное обобщение задачи Упаковки в контейнеры, называемое Vector Packing.

Там размеры всех предметов → d-мерный вектор, контейнеры тоже d-мерный вектора (V,…,V), и цель — упаковать все предметы в минимум контейнеров, так, чтобы упакованные в контейнеро предметы, после векторного суммирования[1], не вылезали за его границы.

Покажите, что приближенный алгоритм, типа First Fit, обобщенный для многомерности,

найдет (d+1)-оптимальное решение.
  1. Т.е. это не как упаковка в многомерном тетрисе