Problema de Empaquetamiento de Bins con tamaño fijo de bins

Question

Estoy estudiando el Problema de Empaquetamiento de Bins para mi tesis y me encontré con esta definición de la versión de decisión del problema en el libro "Computers and Intractability" de Michael R. Garey y David S. Johnson:

INSTANCIA: Un conjunto finito $U$ de ítems, un tamaño $s(u) \in Z$ para cada $u \in U$, una capacidad de bin entera positiva $B$, y un entero positivo $K$.

PREGUNTA: ¿Existe una partición de $U$ en conjuntos disjuntos $U_1, U_2, ..., U_k$ tal que la suma de tamaños de los ítems en cada $U_i$ sea $B$ o menor.

Y hay un comentario curioso sobre su solución en tiempo polinomial, que es "Resoluble en tiempo polinomial para cualquier $B$ fijo mediante búsqueda exhaustiva."

Ahora mi pregunta es cómo es posible, buscando en internet no he encontrado más que esta pregunta: NP-hardness of bin packing problem for fixed bin size pero la respuesta no me convence, parece incorrecta, o tal vez simplemente no la entiendo. ¿Puedes ayudarme con esto?

Answer 1

Con un tamaño de contenedor fijo, también tienes un número fijo de posibles formas de llenar un contenedor (parcialmente). Supongamos que hay $p$ formas de hacerlo.

Si resuelves cada uno de los $k$ contenedores por separado, obtendrías $p$ posibilidades para cada contenedor, y luego $p^k$ posibilidades en total. Esto es exponencial, y no es lo que nos gustaría. Ten en cuenta que muchas de esas posibilidades no coincidirán con los tamaños reales de los elementos que tienes disponibles, por lo que es simplemente un límite superior.

En lugar de asignar una partición a cada contenedor, puedes hacer lo contrario - asignar algunos contenedores (posiblemente cero) a cada partición. Entonces tienes $(k+1)^p$ formas posibles de esa asignación. Esto tiene un exponente fijo, por lo que es polinomial en el número de contenedores. El grado $p$ de este polinomio puede ser enorme, y esto también es un límite superior ya que la mayoría de esas asignaciones tendrán el número total incorrecto de contenedores, pero todo eso no importa - es suficiente con mostrar que es polinomial.

Por ejemplo, supongamos que el tamaño del contenedor es $3$. Solo hay $6$ formas posibles de llenar parcial o completamente un contenedor: $1$, $1+1$, $1+1+1$, $2$, $2+1$, $3$. Sean $a,b,c,d,e,f$ variables que representan cuántos contenedores hay para cada una de esas formas de llenarlos. Cada variable debe tener un valor entero de $0$ a $k$ inclusive. Así que no hay más de $(k+1)^6$ posibilidades para verificar. De hecho, hay muchas menos, ya que también tenemos $a+b+c+d+e+f=k$. Por ejemplo, si queremos verificar si $a=b=c=d=0$, $e=f=4$ es un empaquetado de contenedor válido. Tenemos cuatro contenedores que contienen un elemento de tamaño $2$ y un elemento de tamaño $1$, y cuatro contenedores con un elemento de tamaño $3$. Si tu inventario $U$ contiene cuatro elementos de cada tamaño, entonces tienes un empaquetado válido. No importa cuántos contenedores de tamaño $3$ tengas, solo hay $6$ variables que necesitas determinar, y eso es polinomial en el número de contenedores.