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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Решенные задачи на :Нерешенные задачи)
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
 
Строка 9: Строка 9:
 
найдет (d+1)-оптимальное решение.
 
найдет (d+1)-оптимальное решение.
  
[[Категория:Нерешенные задачи]]
+
[[Категория:Решенные задачи]]

Текущая версия на 15:49, 20 мая 2020

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

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

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

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