Tiene n1 elementos del tamaño s1, n2 elementos del tamaño s2 y n3 elementos del tamaño s3. Desea empacar todos estos elementos en contenedores con capacidad C, de modo que se minimice el número total de contenedores usados.Programación Dinámica de Envases Pregunta
¿Cómo podemos lograr una solución usando un número mínimo de contenedores? Greedy no está funcionando.
No es una pregunta tonta, IMO.
En general, se sabe que el empaque de contenedores es NP-Completo.
Pero en su caso, el embalaje de cubo con un número fijo de pesos de objeto es una variante interesante.
El siguiente artículo afirma tener un algoritmo de tiempo polinomial que viene con 1 de óptimo: http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310 cuando permite 3 tamaños diferentes. (Advertencia: solo voy por el resumen).
Así que supongo que esta versión también es NP-Hard y el algoritmo Greedy probablemente no funcione. No estoy tan seguro de la programación dinámica (el empaque del contenedor es totalmente NP-Completo).
Espero que ayude.
Si usted puede reducir el problema a una 1d bin-embalaje que desee utilizar un algoritmo voraz utilizado aquí: http://www.developerfusion.com/article/5540/bin-packing
Si el tamaño es unidimensional, o si se puede reducir a un valor unidimensional, puede resolver esto como un problema de mochila multi-saco (MKP), donde el peso de un artículo es igual a su beneficio. Si establece #bin en el límite superior para la cantidad de elementos disponibles (de un vistazo, si su instancia no es muy alta, este valor puede ser # elementos), puede resolver este problema de manera óptima con una rama y un límite o otro algoritmo de optimización. Si puede admitir una solución no óptima, hay algunos algoritmos codiciosos factibles.
Sin embargo, no estoy tan seguro ya que nunca he estudiado este problema a fondo. Sin embargo, hay un libro llamado "Knapsack Problems" (Problemas de mochila) que presenta formulaciones y algoritmos, que incluyen problemas de embalaje en el cesto. No es difícil encontrarlo como PDF en Internet.
Espero que esta ayuda. Buena suerte.
El número mínimo de contenedores de embalaje excelente asumiendo sería B = ceiling(sum(n(i)*s(i) for i in 1..3)/C)
utilizan lo que se llama first_fit, pero en realidad es worst_fit, con el intercambio, desde here para ver si los elementos encajan en los compartimientos B. Si no, incremente B y repita hasta que encajen.
No será eficiente, pero puede resolver este
en tiempo polinomial
con un algoritmo de programación dinámico directo.
El grado del polinomio dependerá de la cantidad de tamaños diferentes que tenga.
He incluido una implementación que para 3 tamaños diferentes será O(n1 * n2 * n3 * (C/s2) * (C/s3) * ((n1*s1 + n2*s2 + n3*s3)/C)) con una constante bastante repugnante. (Esa cifra se debe al hecho de que el número de patrones distintos de disponibilidad es O(n1 * n2 * n3) y para cada uno generamos O((C/s2) * (C/s3)) posibles siguientes contenedores para probar, para cada uno de los cuales tenemos que trabajar con un conjunto de contenedores cuyo tamaño es O((n1*s1 + n2*s2 + n3*s3)/C)). Una serie de optimizaciones de rutina podría acelerar masivamente este programa.)
#! /usr/bin/python
import heapq
def min_bins(bin_size, sizes, counts):
available = zip(sizes, counts)
available.sort(reverse=True)
seen = set([])
upcoming = [(0, available, [])]
while 0 < len(upcoming):
(n, available, bins) = heapq.heappop(upcoming)
for (bin, left) in bin_packing_and_left(bin_size, available):
new_bins = bins + [bin]
if 0 == len(left):
return new_bins
elif left not in seen:
heapq.heappush(upcoming, (n+1, left, new_bins))
seen.add(left)
def bin_packing_and_left(bin_size, available, top=True):
if 0 == len(available):
yield ((),())
else:
(size, count) = available[0]
available = available[1:]
for (bin, left, used) in bin_packing_and_left_size(bin_size, available):
can_use = (bin_size - used)/size
if count <= can_use:
yield(((size, count),) + bin, left)
elif 0 < can_use:
yield(((size, can_use),) + bin,
((size, count - can_use),) + left)
else:
yield(bin, ((size, count),) + left)
def bin_packing_and_left_size(bin_size, available):
if 0 == len(available):
yield ((),(), 0)
else:
(size, count) = available[0]
available = available[1:]
for (bin, left, used) in bin_packing_and_left_size(bin_size, available):
for i in range(1 + min(count, (bin_size - used)/size)):
if count == i:
yield(((size, count),) + bin, left, used + size * count)
elif 0 < i:
yield(((size, i),) + bin,
((size, count - i),) + left,
used + size * i)
else:
yield(bin, ((size, count),) + left, used)
answer = min_bins(23, (2, 3, 5), (20, 30, 40))
print len(answer)
print answer
O (C) u O (s1) no es polinomio. El tamaño de la entrada es log (n1 * n2 * n3 * s1 * s2 * s3 * C). Lo que parece haber demostrado es que no es fuertemente NP-Hard. +1 a pesar de :-) –
@Moron: Gah, tienes razón. Me olvido de que pensamos en el tamaño de la entrada en términos de la entrada de bits, y no en el tamaño del número. – btilly
Ejecuté esta implementación en la entrada 'min_bins (6000, (200, 10, 500, 100, 50, 1000), (2, 80, 10, 100, 150, 2))' (que en realidad es el orden de magnitud Necesito por razones prácticas), y me di por vencido después de aproximadamente 10 minutos ya que el proceso consumía más de 2,5 GB de memoria :) –
Aquí hay un boceto del algoritmo DP para este.
Relación recursiva: recursemos en B(i, j, k), el número mínimo de contenedores de capacidad C necesarios para empaquetar i elementos de tamaño s1, j elementos de tamaño s2 yk artículos de tamaño s3. La relación es:
B(i, j, k) = min {B (x,y,z) , B(i-x, j-y, k-z)}
where 0<=x<=i;
0<=y<=j;
0<=z<=k
donde al menos uno de x, y o z debe ser mayor que 0 y uno de x, y o z debe ser menor que i, j o k respectivamente.
Tiempo de ejecución: B es el tamaño O (n3) y el cálculo de cada elemento de B requiere tiempo O (n3) para un tiempo total de O (n6).
Se puede hacer en O(n1*n2*n3) ...
permite decir, sin f(i,j,k) es el mínimo. de contenedores que se requieren para adaptarse i, j y k artículos de tamaño s1, s2, s3 respectivamente ..
Nota: C es la capacidad de la bandeja de
f(i,j,k) llevará a cabo 2 tipos de información:
a) (The min no. of bins that are currently required) - 1. Digamos que la propiedad es B1.
b) El tamaño actual de la última bin que está disponible para su posterior presentación .. dicen que la propiedad es B2 .. donde 0 < B2 <= C
Por lo tanto, la recurrencia sería:
f(i,j,k)([B1],[B2]) =
min
{
f(i-1, j, k)([B1] + [B2 + S1]/(C+1) , [B2 + S1] <=C ? [B2 + S1] : [B2 + S1 - C]) ,
f(i, j-1, k)([B1] + [B2 + S2]/(C+1) , [B2 + S2] <=C ? [B2 + S2] : [B2 + S2 - C]) ,
f(i, j, k-1)([B1] + [B2 + S3]/(C+1) , [B2 + S3] <=C ? [B2 + S3] : [B2 + S3 - C])
}
El mínimo no. de contenedores requeridos: 1 + f(n1, n2, n3)[B1]
Si podemos encontrar la solución óptima para una bandeja, eso significa que la cantidad máxima de elementos que puedo caber en una bandeja, esto llevaría a la respuesta.
Supongamos que un elemento de tamaño S1, b elementos de tamaño S2, c elementos de tamaño S3 son la cantidad máxima de elementos que puedo caber en un contenedor. Así que el tamaño máximo que puedo caber en un bin es K = a * S1 + b * S2 + c * S3.so la respuesta sería (n1 * S1 + n2 * s2 + n3 * s3)/K + (n1 * S1 + n2 * s2 + n3 * s3)% K no de contenedores.
Finding K es más fácil que estándar Knapsack problem.if que supongo que todos los valores óptimos hasta que existe 1 < = i < = C.Then valor óptimo de i + 1 se puede escribir de forma recursiva como
M(i+1) = max(M(i),M(i-S1)+S1,M(i-S2)+S2,M(i-S3)+S3).
¿Cuál es la pregunta? –
¿Tarea para qué clase exactamente? –
@Henk: No es una tarea de todos modos, dejé la universidad hace 6 años. Puede ser una pregunta tonta, pero no pude hacer sub-problemas por mi cuenta. –