Reconocer un problema de DP en Java

Problema

¿Qué pedidos debe aceptar la furgoneta?

Tienes una furgoneta de alquiler. Para mañana hay seis pedidos de transporte, cada uno con un inicio, un fin y un precio. La furgoneta solo puede estar en un lugar, así que dos pedidos que se superponen no pueden aceptarse los dos. ¿Cuáles aceptas para ganar lo máximo?

Lo primero que se le ocurre a cualquiera es una regla voraz: el pedido más caro primero, luego el siguiente que no estorbe. O: el que termina más temprano, para que quede más tiempo:

static List<Job> greedy(Job[] jobs, Comparator<Job> rule) {
    Job[] queue = jobs.clone();
    Arrays.sort(queue, rule);
    List<Job> taken = new ArrayList<>();
    for (Job job : queue) {
        boolean free = true;
        for (Job t : taken) {
            if (job.start() < t.end() && t.start() < job.end()) free = false;
        }
        if (free) taken.add(job);
    }
    return taken;
}

static void show(String rule, List<Job> taken) {
    int sum = taken.stream().mapToInt(Job::pay).sum();
    List<String> names = taken.stream().map(Job::name).toList();
    System.out.println(rule + ": " + String.join(", ", names) + " = " + sum + " €");
}

show("Las más caras primero", greedy(jobs, Comparator.comparingInt(Job::pay).reversed()));
show("El fin más temprano primero", greedy(jobs, Comparator.comparingInt(Job::end)));

Las más caras primero: aeropuerto, sofá = 180 €
El fin más temprano primero: mercado, oficina, reparación = 170 €

Las dos reglas dejan dinero sobre la mesa: hay un plan que vale más. Probar los 2⁶ = 64 subconjuntos funciona aquí, pero con 60 pedidos hay más de un trillón. La tarea es del mismo tipo que la mochila y diff. ¿Cómo lo reconoces tú mismo y cómo construyes la solución?

La idea

Las señales

Una tarea es para la programación dinámica cuando tiene tres cosas:

La pregunta es sobre lo mejor o sobre la cantidad. «Lo máximo», «lo mínimo», «de cuántas formas», «si es posible». Si solo pide «encuentra el elemento» u «ordena», no hay nada que elegir.
Subestructura óptima. La mejor solución del todo se construye con las mejores soluciones de partes más pequeñas. Para la furgoneta: si el último pedido está en el mejor plan, el resto es el mejor plan de los pedidos que terminan antes que él.
Subproblemas superpuestos. Las mismas partes más pequeñas se preguntan muchas veces, como con el Fibonacci ingenuo. En la furgoneta, «reparación» y «aeropuerto» empiezan las dos a las 15:00 y preguntan lo mismo: lo máximo de los pedidos que terminan a las 15:00.

Cuando están las tres, la respuesta para cada parte pequeña se calcula una vez y se anota.

La idea

La receta de cinco pasos

Estado. Qué es una celda: «best[i] es el máximo dinero de los primeros i pedidos, ordenados por su fin». Un buen estado describe la tarea pequeña con uno o dos números.
Transición. Cómo se calcula la celda a partir de otras más pequeñas. Para el pedido i hay dos elecciones: omitirlo (best[i − 1]) o tomarlo (su precio + best[p], donde p es cuántos pedidos terminan hasta su inicio). best[i] es la mayor.
Base. Las celdas que no dependen de nada: best[0] = 0, sin pedidos, sin dinero.
Orden. En qué orden llenar para que lo necesario ya esté hecho: de izquierda a derecha, porque i solo usa i − 1 y p < i.
Respuesta. Qué celda es la respuesta: best[n]. Si además quieres saber cuáles pedidos, vuelves atrás siguiendo las elecciones, como el camino de vuelta en diff.

Ordenar por el fin forma parte del estado: así los pedidos compatibles con el i-ésimo son exactamente los primeros p, y «lo mejor de ellos» es una celda.

Más precisamente, para curiosos

La misma receta funciona también de arriba abajo: una función best(i) que llama a best(i − 1) y a best(p) y recuerda el resultado (ver memoización). La tabla de abajo hacia arriba y la recursión con memoria calculan las mismas celdas. La recursión está más cerca de las palabras de la transición, la tabla no tiene una pila profunda.

En Java la memoización es un Map<Integer, Integer> o un arreglo con -1 para «todavía no calculado». Una recursión profunda puede lanzar StackOverflowError, así que para secuencias largas la tabla es más segura.

p se puede encontrar con búsqueda binaria sobre los fines, porque están ordenados: entonces el total es O(n log n). El bucle de la lección es O(n) por pedido, O(n²) en total, y para seis pedidos sobra.

Míralo

La receta en código

static int bestPay(Job[] jobs) {
    Arrays.sort(jobs, Comparator.comparingInt(Job::end));
    int n = jobs.length;
    int[] best = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        Job job = jobs[i - 1];
        int p = 0;
        while (jobs[p].end() <= job.start()) p++;
        int skip = best[i - 1];
        int take = job.pay() + best[p];
        best[i] = Math.max(skip, take);
    }
    return best[n];
}

Arrays.sort ordena el arreglo en el sitio, y Comparator.comparingInt(Job::end) dice por qué. El bucle de p se detiene a más tardar en el propio pedido i, porque termina después de empezar.

Job[] jobs = {
    new Job("sofá", 9, 12, 80),
    new Job("aeropuerto", 15, 20, 100),
    new Job("mercado", 8, 10, 60),
    new Job("almacén", 12, 17, 30),
    new Job("oficina", 11, 13, 60),
    new Job("reparación", 15, 19, 50),
};
System.out.println("Como máximo: " + bestPay(jobs) + " €");

Como máximo: 220 €

static int bestPay(Job[] jobs) {
    Arrays.sort(jobs, Comparator.comparingInt(Job::end));
    int n = jobs.length;
    int[] best = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        Job job = jobs[i - 1];
        int p = 0;
        while (jobs[p].end() <= job.start()) p++;
        int skip = best[i - 1];
        int take = job.pay() + best[p];
        best[i] = Math.max(skip, take);
    }
    return best[n];
}

Paso a paso, en palabras

Seis pedidos para una furgoneta. Estado: ordénalos por su fin; best[i] es el máximo dinero de los primeros i.
Base: best[0] = 0, sin pedidos no hay dinero. Orden: de izquierda a derecha, cada celda necesita solo celdas a su izquierda.
Pedido 1, mercado 8–10 h, 60 €: ningún pedido termina antes de su inicio, p = 0. Omitir: best[0] = 0. Tomar: 60 + best[0] = 60. Mejor tomarlo: best[1] = 60.
Pedido 2, sofá 9–12 h, 80 €: ningún pedido termina antes de su inicio, p = 0. Omitir: best[1] = 60. Tomar: 80 + best[0] = 80. Mejor tomarlo: best[2] = 80.
Pedido 3, oficina 11–13 h, 60 €: termina uno hasta las 11:00 h, p = 1. Omitir: best[2] = 80. Tomar: 60 + best[1] = 120. Mejor tomarlo: best[3] = 120.
Pedido 4, almacén 12–17 h, 30 €: terminan 2 hasta las 12:00 h, p = 2. Omitir: best[3] = 120. Tomar: 30 + best[2] = 110. Mejor omitirlo: best[4] = 120.
Pedido 5, reparación 15–19 h, 50 €: terminan 3 hasta las 15:00 h, p = 3. Omitir: best[4] = 120. Tomar: 50 + best[3] = 170. Mejor tomarlo: best[5] = 170.
Pedido 6, aeropuerto 15–20 h, 100 €: terminan 3 hasta las 15:00 h, p = 3. Omitir: best[5] = 170. Tomar: 100 + best[3] = 220. Mejor tomarlo: best[6] = 220.
Respuesta: best[6] = 220 €. Siguiendo «tomar» hacia atrás salen los pedidos: mercado, oficina, aeropuerto.

220 € con mercado, oficina y aeropuerto: más que tanto «el más caro primero» como «el fin más temprano primero».

Pruébalo

Encuentra el error

Un compañero copió la transición. El programa dice:

static int bestPay(Job[] jobs) {
    Arrays.sort(jobs, Comparator.comparingInt(Job::end));
    int n = jobs.length;
    int[] best = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        Job job = jobs[i - 1];
        int p = 0;
        while (jobs[p].end() <= job.start()) p++;
        int skip = best[i - 1];
        int take = job.pay() + best[i - 1];
        best[i] = Math.max(skip, take);
    }
    return best[n];
}

Job[] jobs = {
    new Job("sofá", 9, 12, 80),
    new Job("aeropuerto", 15, 20, 100),
    new Job("mercado", 8, 10, 60),
    new Job("almacén", 12, 17, 30),
    new Job("oficina", 11, 13, 60),
    new Job("reparación", 15, 19, 50),
};
System.out.println("Como máximo: " + bestPay(jobs) + " €");

Como máximo: 380 €

Eso es imposible: los seis pedidos juntos no caben en una furgoneta. ¿En qué línea está el error?

Elige la línea con el error.

La idea

Una segunda tarea: estacionar a lo largo de la ruta

Un camión va del almacén a la última parada de estacionamiento de la autopista. El conductor tiene que descansar: desde una parada llega como máximo a la siguiente o a la siguiente de esa. Cada parada tiene una tarifa. ¿Cuánto paga como mínimo, deteniéndose también en la última?

Las señales: «cuánto como mínimo», y el camino más barato a la parada i pasa por el más barato a i − 1 o a i − 2. La receta:

Estado: cost[i] es lo mínimo pagado hasta la parada i, deteniéndose en ella.
Transición: cost[i] = la tarifa de i + min(cost[i − 1], cost[i − 2]).
Base: desde el almacén llega a la parada 0 o va directo a la parada 1, así que cost[0] y cost[1] son simplemente sus tarifas.
Orden: de izquierda a derecha.
Respuesta: el costo de la última parada.

static int minFees(int[] fee) {
    int n = fee.length;
    int[] cost = new int[n];
    cost[0] = fee[0];
    cost[1] = fee[1];
    for (int i = 2; i < n; i++) {
        cost[i] = fee[i] + Math.min(cost[i - 1], cost[i - 2]);
    }
    return cost[n - 1];
}

int[] parking = {4, 9, 3, 12, 5, 2, 10, 6};
System.out.println("Como mínimo: " + minFees(parking) + " €");

Como mínimo: 20 €

Pruébalo

Predice la salida

Cuatro paradas de estacionamiento con tarifas de 5 €, 1 €, 4 € y 2 €:

static int minFees(int[] fee) {
    int n = fee.length;
    int[] cost = new int[n];
    cost[0] = fee[0];
    cost[1] = fee[1];
    for (int i = 2; i < n; i++) {
        cost[i] = fee[i] + Math.min(cost[i - 1], cost[i - 2]);
    }
    return cost[n - 1];
}

int[] parking = {5, 1, 4, 2};
System.out.println("Como mínimo: " + minFees(parking) + " €");

Respuesta

Como mínimo: 8 €

Como mínimo: 3 €

Como mínimo: 12 €

La idea

Una tercera tarea: texto sin espacios

Los clientes escriben «rebajasdeverano» en el cuadro de búsqueda, sin espacios, como en un hashtag. ¿Se puede dividir el texto en palabras del diccionario?

La señal es «si es posible»: sí o no. La receta:

Estado: ok[i] es «las primeras i letras se dividen en palabras».
Transición: ok[i] es verdadero si hay un j < i con ok[j] y las letras de j a i son una palabra del diccionario.
Base: ok[0] es verdadero: el comienzo vacío siempre se divide.
Orden: i crece.
Respuesta: ok[n].

static boolean canSplit(String text, Set<String> words) {
    int n = text.length();
    boolean[] ok = new boolean[n + 1];
    ok[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i && !ok[i]; j++) {
            ok[i] = ok[j] && words.contains(text.substring(j, i));
        }
    }
    return ok[n];
}

Set<String> words = Set.of(
    "verano", "ver", "de", "rebajas", "rebaja", "zapatos", "para", "niños", "niño");
for (String text : List.of("rebajasdeverano", "zapatosparaniños", "zapatosparabebés")) {
    System.out.println(text + ": " + (canSplit(text, words) ? "sí" : "no"));
}

rebajasdeverano: sí
zapatosparaniños: sí
zapatosparabebés: no

Más precisamente, para curiosos

Para cada i el bucle prueba hasta i lugares para j, y cada trozo se corta y se busca en el diccionario. Cortar copia las letras (substring crea una cadena nueva), así que el total es hasta O(n³) para un texto de n letras. Si la palabra más larga del diccionario tiene L letras, j solo necesita estar entre i − L e i, y el tiempo baja a O(n · L²). Los buscadores reales usan un trie con las palabras del diccionario: recorren las letras desde j en adelante y se detienen en cuanto el trie termina.

Pruébalo

Completa la transición

static boolean canSplit(String text, Set<String> words) {
    int n = text.length();
    boolean[] ok = new boolean[n + 1];
    ok[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i && !ok[i]; j++) {
            ok[i] = ;
        }
    }
    return ok[n];
}

La idea

Parece DP, pero no lo es

No toda tarea de «lo máximo» necesita una tabla.

A veces basta lo voraz. Si todos los pedidos de la furgoneta pagan lo mismo, la pregunta pasa a ser «cuántos pedidos como máximo», y la regla «el fin más temprano primero» da exactamente lo mejor, en O(n log n) y sin tabla. Cuándo lo voraz es correcto de forma demostrable y por qué está en el próximo módulo. La señal: en cada paso una elección es siempre al menos tan buena como cualquier otra.
El grafo no tiene orden. El camino más corto en una ciudad parece DP: la distancia a un cruce se construye con las distancias a sus vecinos. Pero las calles forman ciclos, y «hasta A» depende de «hasta B», mientras que «hasta B» depende de «hasta A». No hay un orden para llenar la tabla de izquierda a derecha. Por eso allí es Dijkstra: encuentra el orden sobre la marcha.
Sin superposición. Si los subproblemas no se repiten, como en el ordenamiento por mezcla, recordar no ahorra nada. Eso es divide y vencerás.

La prueba es el paso 4 de la receta: si no puedes decir en qué orden llenar, la tarea probablemente trata de un grafo.

Ejercicio

Los carteles publicitarios

Resuelve la tarea en tu editor.

Carteles. A lo largo del bulevar hay siete carteles publicitarios, numerados desde 1, con un alquiler mensual de 120 €, 90 €, 60 €, 150 €, 80 €, 40 € y 130 €. Dos carteles vecinos se tapan entre sí, así que no se pueden alquilar los dos. Escribe la solución siguiendo la receta: imprime el mayor alquiler y qué carteles alquilar:

Como máximo: 400 €
Carteles: 1, 4, 7

Pista: el estado es «lo máximo de los primeros i carteles», y la transición es la misma elección que para la furgoneta: omitir el cartel i o tomarlo junto con lo mejor hasta i − 2.

Más tareas

De cuántas formas. ¿De cuántas formas puede llegar el camión a la última parada de estacionamiento (una o dos paradas a la vez)? Solo cambia la transición: una suma en lugar de un mínimo.
La división con nombres. Imprime también las palabras de «rebajasdeverano»: guarda para cada ok[i] de dónde vino.
Los pedidos con nombres. Haz que bestPay devuelva también qué pedidos aceptar: vuelve atrás desde best[n], como en la escena.

Test

Ponte a prueba

1. ¿Qué pregunta es más probablemente una tarea de DP?¿Cuántas monedas como mínimo, de 1, 3 y 4 céntimos, suman 6 céntimos?Ordena los productos por precio¿Hay en la lista un pedido con el número 1042?

2. En la tarea de la furgoneta los pedidos están ordenados por su fin. ¿Por qué?Porque la regla voraz también lo haceSin ordenar, el programa no compilaAsí los pedidos que terminan antes del i-ésimo son los primeros de la fila: best[p] los cubre

3. ¿Cuál es la base para el texto sin espacios?ok[n] = trueok[0] = falseok[0] = true: el texto vacío siempre se puede dividir

4. ¿Por qué el camino más corto en la ciudad con Dijkstra no se escribe como una tabla de izquierda a derecha?Porque Dijkstra no busca el más cortoLas calles forman ciclos: no hay un orden en el que cada celda dependa solo de celdas terminadasPorque la tabla sería demasiado grande

5. ¿Se te escapa algo si la transición es take = pay + best[i − 1]?No, solo es más lentoSí: pierdes la base best[0]Sí: puedes tomar un pedido que se superpone con uno ya tomado

Reconocer un problema de DP

Cookies