Embalaje de contenedores decrecientes de primer ajuste

---

First-fit-decreasing (FFD) es un algoritmo para el empaque de contenedores . Su entrada es una lista de elementos de diferentes tamaños. Su salida es un embalaje : una partición de los artículos en contenedores de capacidad fija, de modo que la suma de los tamaños de los artículos en cada contenedor sea como máximo la capacidad. Idealmente, nos gustaría usar la menor cantidad posible de contenedores, pero minimizar la cantidad de contenedores es un problema NP-difícil, por lo que usamos una heurística aproximadamente óptima .

En la descripción estándar, recorremos los elementos una vez, pero mantenemos muchos contenedores abiertos. En la descripción equivalente, recorremos los elementos muchas veces, pero mantenemos solo un contenedor abierto cada vez.

El rendimiento de FFD se analizó en varios pasos. A continuación, indica el número de contenedores utilizados por FFD para el conjunto de entrada S y la capacidad del contenedor C.${\ Displaystyle FFD (S, C)}$

Si hay 4 copias de y 2 copias de en la solución óptima, FFD calculará los siguientes contenedores: ${\ estilo de visualización B_ {1}}$${\ estilo de visualización B_ {2}}$

Es decir, 8 contenedores en total, mientras que el óptimo tiene solo 6 contenedores. Por lo tanto, el límite superior es ajustado, porque . ${\displaystyle 11/9\cdot 6+6/9=72/9=8}$

Este ejemplo se puede extender a todos los tamaños de : ^[5] en la configuración óptima hay 9 k +6 bins: 6 k +4 de tipo B ₁ y 3 k +2 de tipo B ₂ . Pero FFD necesita al menos 11 k +8 contenedores, que es .${\displaystyle {\text{OPT}}(S,C)}$${\displaystyle {\frac {11}{9}}(6k+4)+{\frac {6}{9}}}$

---