homechevron_rightУчебаchevron_rightМатематика

Задача об упаковке в контейнеры

Калькулятор решает задачу об упаковке в контейнеры разными эвристическими алгоритмами. Создано по запросу пользователя.

Тут давеча пользователь Artuem оставил очень интересный запрос — Калькулятор количества целых досок из отрезков.

Приведу его здесь полностью, чтобы не прерывать нить повествования: «Есть некоторое количество отрезков разной длины, необходимо рассчитать минимальное кол-во досок из которых их можно нарезать, или что то типа того :)»

Немного подумав, можно понять, что сие есть не что иное, как формулировка Задачи об упаковке в контейнеры.

Иными словами, имеются контейнеры фиксированного объема и набор предметов произвольного объема (понятно, что объем каждого предмета в отдельности меньше объема контейнера). Требуется упаковать эти предметы в минимальное число контейнеров.

Можно еще привести пример «из жизни» — есть набор файлов (например, кинофильмы) разного размера. Требуется записать весь набор на наименьшее число DVD-дисков. Ну и так далее. Частным случаем этой задачи является задача о рюкзаке, кстати.

Задача эта — NP-полная, то есть для гарантированного нахождения оптимального решения нужен полный перебор. Однако есть эвристические алгоритмы для нахождения подходящего решения. Если повезет, оно будет и оптимальным :)

Ниже калькулятор, а используемые алгоритмы, как водится, описаны под ним. И кстати, хоть на данных по умолчанию некоторые решения совпадают, но алгоритмы все-таки разные, и на других данных различия будут заметны.

Создано на PLANETCALC

Задача об упаковке в контейнеры

Набор элементов для упаковки

Размер элементаКоличество элементов данного размера
Размер страницы:

Знаков после запятой: 2
Next Fit Decreasing
Общее число контейнеров
 
Общее использование контейнеров (%)
 
First Fit Decreasing
Общее число контейнеров
 
Общее использование контейнеров (%)
 
Worst Fit Decreasing
Общее число контейнеров
 
Общее использование контейнеров (%)
 
Best Fit Decreasing
Общее число контейнеров
 
Общее использование контейнеров (%)
 



Начнем с Next Fit Algorithm (не уверен, как это переводится в соответствующей литературе, поэтому буду давать английские названия)

Next Fit Algorithm
Алгоритм очень туп, и в большинстве случаев даст наихудшие результаты из всех рассматриваемых алгоритмов.
Суть алгоритма в следующем:

  1. Берем новый элемент.
  2. Берем новый контейнер.
  3. Кладем элемент в контейнер.
  4. Берем следующий элемент.
  5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, идем на шаг 2.

То есть мы тупо кладем элементы в контейнер, и если некий элемент уже не влазит, берем новый контейнер.
Можно придумать алгоритм и похитрее, но у этого алгоритма есть один плюс — он не требует просмотра прошлых контейнеров. Это может оказаться полезным, если, например, контейнеры к нам подъезжают по конвейеру.

First Fit Algorithm
Суть алгоритма в следующем:

  1. Берем новый элемент.
  2. Берем новый контейнер.
  3. Кладем элемент в контейнер.
  4. Берем следующий элемент.
  5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, проверяем остальные контейнеры по порядку. Если находится контейнер с достаточным количеством свободного места, кладем элемент в контейнер и идем на шаг 4, иначе идем на шаг 2.

То есть кладем элементы в контейнер, и если элемент уже не влазит, пытаемся найти подходящий контейнер среди уже частично заполненных. Если места не находим, берем новый контейнер.

Worst Fit Algorithm
Суть алгоритма в следующем:

  1. Берем новый элемент.
  2. Берем новый контейнер.
  3. Кладем элемент в контейнер.
  4. Берем следующий элемент.
  5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, берем частично заполненный контейнер с максимумом свободного места. Если элемент влазит в контейнер, кладем элемент в контейнер и идем на шаг 4, иначе идем на шаг 2.

То есть кладем элементы в контейнер, и если элемент уже не влазит, пытаемся положить его в наименее заполненных контейнер. Если это сделать не удается, берем новый контейнер.

Best Fit Algorithm
Суть алгоритма в следующем:

  1. Берем новый элемент.
  2. Берем новый контейнер.
  3. Кладем элемент в контейнер.
  4. Берем следующий элемент.
  5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, берем частично заполненный контейнер с минимумом свободного места, но в который еще можно положить данный элемент. Если такой контейнер находится, идем на шаг 3, иначе идем на шаг 2.

То есть кладем элементы в контейнер, и если элемент уже не влазит, пытаемся положить его в наиболее заполненных контейнер, но в котором еще есть достаточно места для этого элемента. Если это сделать не удается, берем новый контейнер.

Также надо упомянуть и о том, что для каждого алгоритма есть вариант с предварительной сортировкой элементов по уменьшению — First Fit Decreasing, Best Fit Decreasing и т. п. То есть все тоже самое, только элементы берутся, начиная с самого крупного. Получается, я рассмотрел аж восемь алгоритмов. Но в калькуляторе используются только четыре - все варианты с предварительной сортировкой, ибо они дают лучшие результаты.

Комментарии