Aquí hay un impuesto especial del libro "Algorithm Design Manual".Algoritmo - Bin-packing, arregla contenedores para empacar n objetos
En el problema del empaquetamiento de contenedores, nos dan n objetos metálicos, cada uno pesa entre cero y un kilogramo. Nuestro objetivo es encontrar el menor número de contenedores que contendrán los n objetos, con cada contenedor con un kilogramo como máximo.
La heurística de mejor ajuste para el embalaje de la bandeja es la siguiente. Considere los objetos en el orden en el que se proporcionan. Para cada objeto, coloque en el contenedor parcialmente lleno con la cantidad más pequeña de habitación después de insertar el objeto. Si no existe dicho contenedor, inicie un nuevo contenedor . Diseñe un algoritmo que implemente la heurística de ajuste óptimo (tomando como entrada los n pesos w1, w2, ..., wn y dando como resultado el número de los intervalos utilizados) en el tiempo O (nlogn).
Bien, este impuesto no parece difícil. Mi comprensión inicial es que para el enfoque heurístico que mejor se ajusta, cada vez busco una papelera con el mínimo espacio disponible e intento introducir el objeto. Si el objeto no cabe en la papelera con espacio mínimo, creo una nueva compartimiento.
Puedo construir una BST para almacenar los contenedores y cada vez que un objeto se coloca en un contenedor, puedo eliminar ese contenedor del árbol, actualizar el espacio disponible del contenedor y volver a insertar el contenedor en el árbol. Esto generará O (logN) para cada colocación de objetos.
Sin embargo, noté la parte en negrita y cursiva del impuesto "Para cada objeto, colóquelo en el contenedor parcialmente lleno con la menor cantidad de espacio adicional después de insertar el objeto".
Esto significa que no estoy buscando un contenedor con el mínimo espacio disponible, sino que estoy buscando uno que, si coloque el objeto actual, el espacio disponible resultante (después de colocar el objeto) sea mínimo.
Por ejemplo, si el espacio actual de bin1 es 0.5, bin2 es 0.7. Entonces actualmente, bin1 es el mínimo. Pero si el objeto actual es 0.6, entonces el objeto no puede ser colocado en bin1, en lugar de crear un nuevo bin, tengo que encontrar bin2 para poner el objeto como bin2 - object = 0.7 - 0.5 = 0.2 que es entonces mínimo.
¿Estoy en lo cierto? ¿La parte audaz de la declaración realmente significa lo que pensaba? ¿O es tan simple como "encontrar un contenedor con espacio mínimo, si puede colocar el objeto, luego colocarlo, si no puede, crear un nuevo contenedor"?
Gracias
Editar: la adición de parte de mi código java para mi nueva comprensión de la parte en negrita.
public void arrangeBin(float[] w) {
BST bst = new BST();
bst.root = new Node();
int binCount = 0;
for (int i = 0;i < w.length;i++) {
float weight = w[i];
Node node = bst.root;
float minDiff = 1;
Node minNode = null;
while(node!=null) {
if (node.space > weight) {
float diff = node.space - weight;
if (minDiff > diff) {
minDiff = diff;
minNode = node;
node = node.left;
}
}
else
node = node.right;
}
if (minNode == null) {
binCount++;
Node node = new Node();
node.space -= weight;
bst.insert(node);
}
else {
minNode.space -= weight;
bst.delete(minNode);
bst.insert(minNode);
}
}
}
Su código pasa por todos los nodos para cada nuevo peso, lo que daría como resultado un tiempo de ejecución de O (N2). Si quieres alcanzar O (nlogn) deberías usar algo como lo sugerí en mi respuesta. aparte de eso, parece correcto. – WeaselFox
@WeaselFox, me quedé un bst –