Búsqueda binaria sobre la respuesta
En resumen: La búsqueda binaria sobre la respuesta encuentra el valor más pequeño (como una capacidad) para el que la comprobación «¿alcanza?» se cumple, cuando las respuestas forman una fila «no… no, sí… sí».
Problema
Qué camión alquilar
La empresa de mensajería reparte los paquetes a lo largo de una ruta: en orden, el orden en que están por el camino. El camión sale una vez al día y carga los paquetes uno tras otro hasta que el siguiente no cabe. Ese espera hasta mañana. Los ocho paquetes pesan 6, 9, 4, 7, 3, 8, 5 y 2 kg y deben llegar a los clientes en 3 días.
Cuanto más grande el camión, más alto el alquiler diario. Buscas la capacidad más pequeña con la que los paquetes llegan a tiempo. La primera solución que viene a la mente: probar cada capacidad por turno, desde el paquete más pesado hacia arriba.
static int days(int[] weights, int capacity) { int days = 1; int load = 0; for (int weight : weights) { if (load + weight > capacity) { days++; load = 0; } load += weight; } return days;}int[] weights = {6, 9, 4, 7, 3, 8, 5, 2};int capacity = Arrays.stream(weights).max().getAsInt();int tries = 1;while (days(weights, capacity) > 3) { capacity++; tries++;}System.out.println("Intentos: " + tries);System.out.println("Capacidad: " + capacity + " kg");Intentos: 7Capacidad: 15 kgCon ocho paquetes son 7 intentos. Pero el almacén de la ciudad tiene 1000 paquetes al día (de 1 a 30 kg) durante 5 días laborables. Uno por uno, las comprobaciones cargan 3 089 000 paquetes antes de llegar a la respuesta, y con el doble de paquetes el trabajo crece unas cuatro veces. Lo medirás más abajo.
La idea
Lo ordenado es la respuesta
Los paquetes no están ordenados. Otra cosa sí lo está. Pregunta a cada capacidad «¿alcanza?» y alinea las respuestas:
int[] weights = {6, 9, 4, 7, 3, 8, 5, 2};for (int capacity = 9; capacity <= 18; capacity++) { int d = days(weights, capacity); String answer = d <= 3 ? "sí" : "no"; System.out.printf("%2d kg: %d días, %s%n", capacity, d, answer);} 9 kg: 7 días, no10 kg: 6 días, no11 kg: 5 días, no12 kg: 5 días, no13 kg: 5 días, no14 kg: 5 días, no15 kg: 3 días, sí16 kg: 3 días, sí17 kg: 3 días, sí18 kg: 3 días, síLas respuestas son «no», «no», … y después solo «sí». Una vez que la capacidad X alcanza, cualquier mayor también alcanza: un camión más grande puede llevar exactamente las mismas cargas. Una comprobación así se llama monótona: a partir de cierto punto, la respuesta no cambia.
Y en una fila «no… no, sí… sí» el primer «sí» se encuentra con búsqueda binaria, igual que el primer precio ≥ 20 € en la lección anterior: pruebas la mitad y descartas la otra mitad. Esto es búsqueda binaria sobre la respuesta: no buscas en un arreglo, buscas en el rango de respuestas posibles.
El rango está claro. La capacidad es al menos el paquete más pesado, si no ese paquete nunca cabe. Y no necesita ser más que la suma de todos: entonces todo sale en un día.
Míralo
Las pruebas a lo largo de la fila
static int minCapacity(int[] weights, int maxDays) { int lo = Arrays.stream(weights).max().getAsInt(); int hi = Arrays.stream(weights).sum(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (days(weights, mid) <= maxDays) { hi = mid; } else { lo = mid + 1; } } return lo;}int[] weights = {6, 9, 4, 7, 3, 8, 5, 2};System.out.println("La capacidad más pequeña: " + minCapacity(weights, 3) + " kg");La capacidad más pequeña: 15 kgstatic int days(int[] weights, int capacity) { int days = 1; int load = 0; for (int weight : weights) { if (load + weight > capacity) { days++; load = 0; } load += weight; } return days;}
static int minCapacity(int[] weights, int maxDays) { int lo = Arrays.stream(weights).max().getAsInt(); int hi = Arrays.stream(weights).sum(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (days(weights, mid) <= maxDays) { hi = mid; } else { lo = mid + 1; } } return lo;}Paso a paso, en palabras
- 8 paquetes, como máximo 3 días. La capacidad es al menos 9 kg (el paquete más pesado) y como máximo 44 kg (todo en un día). La respuesta es uno de estos 36 valores.
- mid = 26 kg: el camión carga en orden, 2 días. 2 ≤ 3: sí. Toda capacidad por encima de 26 también es un «sí», por eso hi = 26.
- mid = 17 kg: el camión carga en orden, 3 días. 3 ≤ 3: sí. Toda capacidad por encima de 17 también es un «sí», por eso hi = 17.
- mid = 13 kg: 5 días, más de 3: no. Toda capacidad por debajo de 13 también es un «no», por eso lo = 14.
- mid = 15 kg: el camión carga en orden, 3 días. 3 ≤ 3: sí. Toda capacidad por encima de 15 también es un «sí», por eso hi = 15.
- mid = 14 kg: 5 días, más de 3: no. Toda capacidad por debajo de 14 también es un «no», por eso lo = 15.
- lo y hi se encuentran en 15 kg: el primer «sí» de la fila. 5 comprobaciones en lugar de probar las capacidades una por una.
Este es el límite inferior de la lección anterior. Solo que en lugar de prices[mid] < target hay una pregunta que responde toda una función: days(weights, mid) <= maxDays. Si la respuesta es «sí», mid puede ser el «sí» más pequeño y se queda: hi = mid. Si es «no», mid y todo lo que está por debajo se van: lo = mid + 1.
La comprobación days recorre los n paquetes, y hay unas log₂ del peso total pruebas. En total O(n log S), donde S es el total. Uno por uno serían hasta S pruebas de n paquetes cada una.
Pruébalo
Predice la respuesta
Los mismos ocho paquetes, pero ahora para 8 días. ¿Qué imprime el programa?
int[] weights = {6, 9, 4, 7, 3, 8, 5, 2};System.out.println("La capacidad más pequeña: " + minCapacity(weights, 8) + " kg");lo empieza en el paquete más pesado, 9 kg, y con 9 kg los paquetes salen en 7 días: 7 ≤ 8, o sea «sí». Cada prueba siguiente dice «sí», hi baja hasta lo y la respuesta es 9 kg. Menos es imposible: el paquete de 9 kg no cabría en el camión.
Pruébalo
Completa
La comprobación dice «sí»: con la capacidad mid los paquetes llegan a tiempo. ¿Qué pasa con hi?
static int minCapacity(int[] weights, int maxDays) {
int lo = Arrays.stream(weights).max().getAsInt();
int hi = Arrays.stream(weights).sum();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (days(weights, mid) <= maxDays) {
hi = ;
} else {
lo = mid + 1;
}
}
return lo;
}mid alcanza, pero puede ser la más pequeña que alcanza. Así que se queda en el rango: hi = mid. Todo lo que está por encima se va, porque ahí la respuesta es seguro «sí», y no es la más pequeña.
Pruébalo
Encuentra el error
Los paquetes tienen que llegar en 6 días. La búsqueda dice 9 kg, pero con 9 kg tardan 7 días:
int[] weights = {6, 9, 4, 7, 3, 8, 5, 2};System.out.println("La capacidad más pequeña: " + minCapacity(weights, 6) + " kg");System.out.println(days(weights, minCapacity(weights, 6)) + " días");La capacidad más pequeña: 9 kg7 díasElige la línea con el error.
Con «sí», mid puede ser la respuesta, y hi = mid - 1 la descarta. Aquí la respuesta es 10 kg: la prueba en 10 dice «sí», hi pasa a 9, y en el rango solo queda 9, que es un «no». El bucle termina sin comprobarlo. La corrección es hi = mid: es el rango semiabierto de la lección de búsqueda binaria, y allí también la mitad se queda con «sí».
La idea
Cómo reconocer una tarea así
Hay tres señales:
- buscas el X más pequeño (o más grande) para el que algo es posible;
- para un X dado la comprobación es barata: una pasada, como
days; - la comprobación es monótona: una vez que X funciona, cualquier X mayor también funciona (o cualquier menor).
Entonces no buscas una fórmula para X. Buscas de forma binaria en el rango de X posibles, y la comprobación te dice hacia dónde ir.
Tareas del mismo tipo:
- el menor tiempo en el que tres impresoras de distinta velocidad imprimen 500 etiquetas de paquete. Para un tiempo dado cuentas cuántas etiquetas salen, y más tiempo nunca da menos;
- la menor velocidad de la cinta del almacén con la que los paquetes de un turno pasan en 8 horas;
- la mayor distancia entre los casilleros de paquetes a lo largo del bulevar (el ejercicio de abajo). Aquí buscas el mayor «sí».
Más precisamente, para curiosos
Por qué la comprobación carga «todo lo que cabe». Si el camión hoy lleva menos de lo que puede, queda más para mañana. Llenarlo nunca perjudica, así que el número de días que devuelve days es el menor posible para esa capacidad.
El mayor «sí». Cuando la fila es «sí… sí, no… no» y quieres el último «sí», con «sí» escribes lo = mid, y con «no» hi = mid - 1. Entonces la mitad tiene que redondear hacia arriba: lo + (hi - lo + 1) / 2. Si no, con lo y hi juntos la mitad es lo, lo = mid no se mueve y el bucle no termina nunca. Es el mismo límite de la lección de búsqueda binaria, desde el otro lado.
Una respuesta con fracción. Si X es, por ejemplo, una velocidad en metros por segundo, el rango está hecho de números reales y lo y hi nunca llegan a ser iguales. Entonces el bucle se ejecuta un número fijo de veces, por ejemplo 60: cada vez el rango se reduce a la mitad, y tras 60 reducciones es menor que cualquier precisión que te importe.
Míralo
Mide: uno por uno contra binaria
Paquetes de 1 a 30 kg, 5 días. La operación es un paquete cargado durante una comprobación. Uno por uno, el número de pruebas crece con n, y cada una carga n paquetes: O(n²). La binaria hace unas log₂ S pruebas: O(n log n).
- Cada capacidad, una por una
O(n²) - Búsqueda binaria sobre la capacidad
O(n log n)
| Algoritmo | n = 10 | n = 100 | n = 1000 | n = 10.000 | n = 100.000 |
|---|---|---|---|---|---|
| Cada capacidad, una por una | 90 | 28.800 | 3.089.000 | ≈ 308.900.000 | ≈ 30.890.000.000 |
| Búsqueda binaria sobre la capacidad | 70 | 1100 | 14.000 | 180.000 | 2.100.000 |
static int minCapacity(int[] weights, int maxDays) { int lo = Arrays.stream(weights).max().getAsInt(); int hi = Arrays.stream(weights).sum(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (days(weights, mid) <= maxDays) { hi = mid; } else { lo = mid + 1; } } return lo;}Con 1000 paquetes son 3 089 000 contra 14 000. Por encima de 1000 paquetes, «uno por uno» no se ejecuta de verdad: cargaría cientos de millones de paquetes.
Ejercicio
Los casilleros de paquetes del bulevar
Resuélvelo en tu propio editor.
Lo más separados posible. A lo largo del bulevar hay siete sitios para casilleros de paquetes, a 100, 400, 900, 1200, 2000, 2400 y 3100 m desde el inicio. La empresa instala 3 casilleros y quiere que los dos más cercanos estén lo más lejos posible, para cubrir más ciudad. ¿Cuál es la mayor distancia mínima posible?
Escribe una comprobación canPlace(spots, lockers, gap): pone un casillero en el primer sitio, y cada siguiente en el primer sitio que esté al menos gap metros después de la anterior, y dice si alcanzan para todos. Busca de forma binaria el mayor gap para el que la comprobación dice «sí».
La mayor distancia mínima: 1100 mMás tareas
- Las impresoras. Tres impresoras imprimen una etiqueta en 2, 3 y 7 segundos. ¿En cuántos segundos como mínimo imprimen 500 etiquetas?
- Los mensajeros. Cada mensajero trabaja como máximo 8 horas y toma los pedidos por turno. Los pedidos duran 2, 3, 1, 4, 2, 5, 3 y 2 horas. ¿Cuántos mensajeros hacen falta como mínimo? ¿Y si el turno es de 6 horas?
- Cuántas pruebas. Añade un contador de pruebas a
minCapacityy compáralo con el número de pruebas de uno por uno para los mismos paquetes.
Test