El problema de la mochila en Java

Problema

Qué paquetes van en la caja

Un mensajero va en una bicicleta de carga, y su caja lleva hasta 50 kg. En el almacén esperan paquetes. Cada uno tiene un peso y una tarifa de entrega, y el mensajero cobra la tarifa de cada paquete entregado. Un paquete no se puede partir: se lleva entero o no se lleva. ¿Qué paquetes debe llevar el mensajero para ganar lo máximo?

El programador lo prueba todo: para cada paquete, «llevar» o «dejar». Cuando cada paquete está decidido, el programa comprueba si la carga cabe y cuánto paga. Los paquetes vienen del almacén. Aquí los construimos con una fórmula para que sean iguales en todos los lenguajes: peso de 1 a 20 kg, tarifa de 2 a 40 €.

static long tries = 0;

static int tryAll(int[] weight, int[] fee, int cap, int i, int load, int sum) {
    if (i == weight.length) {
        tries++;
        return load <= cap ? sum : -1;
    }
    int skip = tryAll(weight, fee, cap, i + 1, load, sum);
    int take = tryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]);
    return Math.max(skip, take);
}

for (int n : new int[] {10, 20}) {
    int[] weight = new int[n];
    int[] fee = new int[n];
    for (int i = 0; i < n; i++) {
        weight[i] = 1 + i * 7 % 20;
        fee[i] = 2 + i * 11 % 39;
    }
    tries = 0;
    int best = tryAll(weight, fee, 50, 0, 0, 0);
    System.out.println(n + " paquetes: " + best + " €, " + tries + " combinaciones");
}

10 paquetes: 169 €, 1024 combinaciones
20 paquetes: 208 €, 1048576 combinaciones

Cada paquete duplica las combinaciones: 10 paquetes dan 1024, 20 dan más de un millón. Con 30 paquetes son más de mil millones, y con 50 paquetes son 1 125 899 906 842 624. A mil millones de combinaciones por segundo son unos 13 días, y el mensajero sale a las ocho de la mañana.

La idea

Una tabla de paquetes × kilogramos

La recursión hace una y otra vez las mismas preguntas: «lo mejor desde el paquete 7 con 23 kg de espacio» aparece por muchos caminos distintos. La memoria sobre el par (paquete, espacio) pondría fin a las repeticiones. Pero aquí también es más sencilla la tabla de abajo hacia arriba, y ya la conoces. Solo que esta vez un subproblema tiene dos números: cuántos paquetes miras y cuántos kilogramos de espacio tienes. La tabla es bidimensional.

Las cuatro cosas de la tabla:

Qué significa una celda. best[i][w] es la mayor tarifa con los primeros i paquetes y una carga de como máximo w kg.
De dónde viene. O el paquete i no entra, y entonces es best[i − 1][w]. O entra: su tarifa más best[i − 1][w − su peso], lo mejor sin él para los kilogramos que quedan. La celda se queda con la mayor.
En qué orden se llena. Fila por fila: cada fila lee solo la fila de arriba.
Dónde está la respuesta. Abajo a la derecha: todos los paquetes, toda la carga. El comienzo es la fila 0, sin paquetes: 0 en todas partes.

Este es el problema de la mochila (mochila 0/1): cosas con un peso y un valor, espacio con un límite, y cada cosa se toma entera o no se toma. Elige paquetes para un recorrido, tareas para un sprint con horas limitadas, anuncios para un tiempo de emisión limitado.

Míralo

Llevar o dejar

El último recorrido del día: en la caja quedan 6 kg de espacio y esperan cuatro paquetes. Fíjate en las dos celdas que lee cada celda: la de arriba («dejar») y la flecha de la fila de arriba con la tarifa («llevar»):

static List<Integer> pack(int[] weight, int[] fee,
        int cap) {
    int n = weight.length;
    int[][] best = new int[n + 1][cap + 1];
    for (int i = 1; i <= n; i++) {
        int kg = weight[i - 1];
        int paid = fee[i - 1];
        for (int w = 0; w <= cap; w++) {
            best[i][w] = best[i - 1][w];
            if (kg <= w) {
                int take = best[i - 1][w - kg] + paid;
                best[i][w] = Math.max(best[i][w], take);
            }
        }
    }
    List<Integer> taken = new ArrayList<>();
    for (int i = n, w = cap; i > 0; i--) {
        if (best[i][w] != best[i - 1][w]) {
            taken.add(0, i);
            w -= weight[i - 1];
        }
    }
    return taken;
}

Paso a paso, en palabras

pack(weight, fee, 6): best[i][w] es la mayor tarifa con los primeros i paquetes y como máximo w kg. La fila 0 no tiene paquetes, por eso solo hay ceros.
Dejar el paquete i: lo mejor se queda en lo que la fila de arriba tiene para los mismos kg, best[i − 1][w]. El paquete 1 pesa 4 kg, así que por debajo de 4 kg solo hay eso.
Llevar el paquete i: su tarifa más lo mejor de la fila de arriba para los kg que quedan, best[i − 1][w − kg]. Con 4 kg: 10 € + 0 = 10 € supera a 0.
Fila 3, 6 kg: el paquete 3 (3 kg, 6 €) más lo mejor para 3 kg sin él, 7 €: 13 € > 10 €. Dos paquetes más baratos superan al más caro por kg.
Hacia atrás desde la esquina inferior derecha: igual que arriba significa que el paquete se dejó, distinto significa que se llevó. Paquete 4 no tomado, paquete 3 tomado, paquete 2 tomado, paquete 1 no tomado: 2 + 3 = 13 €.

int[] weight = {4, 3, 3, 1};
int[] fee = {10, 7, 6, 2};
System.out.println(pack(weight, fee, 6));

[2, 3]

La idea

Qué paquetes

La tabla dice cuánto, y el mensajero necesita saber cuáles. La respuesta está en la propia tabla. Empiezas en la esquina inferior derecha. Si la celda es igual a la de arriba, el paquete i no hace falta para ella: subes una fila. Si es distinta, el paquete i se tomó: subes una fila y te mueves a la izquierda según su peso. Y así hasta la fila 0.

Los 20 paquetes de hoy y una caja de 50 kg:

static int paid(int[] fee, List<Integer> taken) {
    int sum = 0;
    for (int p : taken) {
        sum += fee[p - 1];
    }
    return sum;
}

int[] weight = new int[20];
int[] fee = new int[20];
for (int i = 0; i < 20; i++) {
    weight[i] = 1 + i * 7 % 20;
    fee[i] = 2 + i * 11 % 39;
}
List<Integer> taken = pack(weight, fee, 50);
String list = taken.stream().map(String::valueOf).collect(Collectors.joining(" + "));
System.out.println(list + ": " + paid(fee, taken) + " €");

1 + 4 + 7 + 8 + 10 + 11 + 13 + 14: 208 €

Los paquetes pesan 48 kg y pagan 208 €, lo máximo de todas las más de un millón de combinaciones. La tabla tiene 20 filas de paquetes con 51 celdas cada una, 1020 celdas en total.

Pruébalo

Completa

El paquete i entra. ¿Cuántos kilogramos quedan para los demás paquetes?

static List<Integer> pack(int[] weight, int[] fee,
        int cap) {
    int n = weight.length;
    int[][] best = new int[n + 1][cap + 1];
    for (int i = 1; i <= n; i++) {
        int kg = weight[i - 1];
        int paid = fee[i - 1];
        for (int w = 0; w <= cap; w++) {
            best[i][w] = best[i - 1][w];
            if (kg <= w) {
                int take = best[i - 1][] + paid;
                best[i][w] = Math.max(best[i][w], take);
            }
        }
    }
    List<Integer> taken = new ArrayList<>();
    for (int i = n, w = cap; i > 0; i--) {
        if (best[i][w] != best[i - 1][w]) {
            taken.add(0, i);
            w -= weight[i - 1];
        }
    }
    return taken;
}

La idea

Por qué no el más caro por kilogramo

Parece sensato: calculas la tarifa por kilogramo de cada paquete y tomas el más caro que quepa, luego el siguiente. En el recorrido de 6 kg el paquete 1 cuesta 2,50 € por kilogramo, el paquete 2 unos 2,33, el paquete 3 2 y el paquete 4 2.

static List<Integer> greedy(int[] weight, int[] fee, int cap) {
    boolean[] used = new boolean[weight.length];
    List<Integer> taken = new ArrayList<>();
    while (true) {
        int pick = -1;
        double rate = 0;
        for (int i = 0; i < weight.length; i++) {
            double perKg = (double) fee[i] / weight[i];
            if (!used[i] && weight[i] <= cap && perKg > rate) {
                pick = i;
                rate = perKg;
            }
        }
        if (pick < 0) {
            return taken;
        }
        used[pick] = true;
        taken.add(pick + 1);
        cap -= weight[pick];
    }
}

int[] weight = {4, 3, 3, 1};
int[] fee = {10, 7, 6, 2};
List<Integer> fast = greedy(weight, fee, 6);
List<Integer> best = pack(weight, fee, 6);
String a = fast.stream().map(String::valueOf).collect(Collectors.joining(" + "));
String b = best.stream().map(String::valueOf).collect(Collectors.joining(" + "));
System.out.println("por €/kg: " + a + " = " + paid(fee, fast) + " €");
System.out.println("tabla: " + b + " = " + paid(fee, best) + " €");

por €/kg: 1 + 4 = 12 €
tabla: 2 + 3 = 13 €

El paquete 1 entra primero y ocupa 4 kg. Quedan 2 kg, y solo cabe el paquete 4. Los paquetes 2 y 3 habrían llenado los 6 kg por completo y habrían pagado más. La regla elige sin mirar atrás, y su primera elección deja fuera la combinación mejor. La tabla prueba las dos opciones para cada paquete y cada cantidad de espacio.

Si los paquetes se pudieran cortar (arena, combustible), «el más caro por kilogramo primero» sería correcto. Cuándo funciona una regla así y cuándo falla es la lección «Cuándo falla un algoritmo voraz».

La idea

Una fila en lugar de una tabla

Cada fila lee solo la fila de arriba. Así que no necesitas toda la tabla: basta una fila best[0..W], sobrescrita paquete tras paquete. Cuando solo hace falta el total, el programa se acorta:

static int bestFee(int[] weight, int[] fee, int cap) {
    int[] best = new int[cap + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = cap; w >= weight[i]; w--) {
            int take = best[w - weight[i]] + fee[i];
            best[w] = Math.max(best[w], take);
        }
    }
    return best[cap];
}

int[] weight = {4, 3, 3, 1};
int[] fee = {10, 7, 6, 2};
System.out.println(bestFee(weight, fee, 6) + " €");

13 €

Lo importante es la dirección: los kilogramos van de arriba abajo, desde W hasta el peso del paquete. La celda w lee best[w − peso], que está a su izquierda. De arriba abajo esa celda todavía no se ha sobrescrito en esta ronda, así que viene de la fila de arriba, sin el paquete actual. Así el paquete entra como máximo una vez.

Pruébalo

Predice la salida

5 kg de espacio y tres paquetes: 2 kg por 3 €, 3 kg por 4 €, 4 kg por 5 €. ¿Qué imprime el programa?

static int bestFee(int[] weight, int[] fee, int cap) {
    int[] best = new int[cap + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = cap; w >= weight[i]; w--) {
            int take = best[w - weight[i]] + fee[i];
            best[w] = Math.max(best[w], take);
        }
    }
    return best[cap];
}

int[] weight = {2, 3, 4};
int[] fee = {3, 4, 5};
System.out.println(bestFee(weight, fee, 5) + " €");

Respuesta

8 €

7 €

5 €

Pruébalo

Encuentra el error

Un compañero dio la vuelta a la dirección de los kilogramos. Para el recorrido de 6 kg su programa dice:

int[] weight = {4, 3, 3, 1};
int[] fee = {10, 7, 6, 2};
System.out.println(bestFee(weight, fee, 6) + " €");

14 €

Y lo mejor son 13 €. ¿Qué línea tiene el error?

Elige la línea con el error.

Míralo

Mídelo: todas las combinaciones frente a la tabla

Contamos las combinaciones comprobadas y las comparaciones «llevar o dejar» en la fila. La caja es de 50 kg. Por encima de 20 paquetes las combinaciones no se ejecutan: son exactamente 2ⁿ, así que la estimación con «≈» es exacta.

Cada combinación O(2ⁿ)
Tabla (hasta 50 kg) O(n)

Algoritmo	n = 10	n = 20	n = 30	n = 40
Cada combinación	1024	1.048.576	≈ 1.073.741.824	≈ 1.099.511.627.776
Tabla (hasta 50 kg)	425	810	1235	1620

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

static int bestFee(int[] weight, int[] fee, int cap) {
    int[] best = new int[cap + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = cap; w >= weight[i]; w--) {
            int take = best[w - weight[i]] + fee[i];
            best[w] = Math.max(best[w], take);
        }
    }
    return best[cap];
}

Cada paquete nuevo duplica las combinaciones y añade una fila a la tabla: como máximo 50 comparaciones. Con 40 paquetes la tabla hace 1620 comparaciones, mientras que las combinaciones son más de un billón. Por eso la tabla crece también en línea recta: con 50 kg fijos es O(n). El precio de W está en «Más precisamente», más abajo.

Más precisamente, para curiosos

Los mismos números en tu lenguaje:

static long tries = 0;

static int tryAll(int[] weight, int[] fee, int cap, int i, int load, int sum) {
    if (i == weight.length) {
        tries++;
        return load <= cap ? sum : -1;
    }
    int skip = tryAll(weight, fee, cap, i + 1, load, sum);
    int take = tryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]);
    return Math.max(skip, take);
}

static int bestFee(int[] weight, int[] fee, int cap) {
    int[] best = new int[cap + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = cap; w >= weight[i]; w--) {
            tries++;
            int take = best[w - weight[i]] + fee[i];
            best[w] = Math.max(best[w], take);
        }
    }
    return best[cap];
}

for (int n : new int[] {10, 20}) {
    int[] weight = new int[n];
    int[] fee = new int[n];
    for (int i = 0; i < n; i++) {
        weight[i] = 1 + i * 7 % 20;
        fee[i] = 2 + i * 11 % 39;
    }
    tries = 0;
    tryAll(weight, fee, 50, 0, 0, 0);
    long all = tries;
    tries = 0;
    bestFee(weight, fee, 50);
    System.out.println(n + " paquetes: combinaciones " + all + ", tabla " + tries);
}

10 paquetes: combinaciones 1024, tabla 425
20 paquetes: combinaciones 1048576, tabla 810

Ejercicio

El recorrido de la entrada

Resuélvelo en tu editor.

Recorrido. Lee la carga en kg en la primera línea, los pesos de los paquetes en la segunda y las tarifas en la tercera. Imprime qué paquetes debe llevar el mensajero y cuánto paga eso. Usa pack y paid de la lección.

15
5 6 3 4 7 2
11 14 6 9 15 3

1 + 2 + 4: 34 €

Más tareas

Y cuántos kg. Imprime también cuánto pesan los paquetes tomados y cuánto espacio queda.
Paquetes urgentes. El paquete 2 tiene que salir sí o sí. ¿Cómo lo metes en el problema sin escribir una tabla nueva? (Pista: quítalo de la lista y baja la carga en su peso.)
Dos cajas. La bicicleta tiene dos cajas de 25 kg. ¿Por qué no basta con resolver el problema para 50 kg?

Más precisamente

Más precisamente: el precio de W

Por qué «O(n · W)» no significa «siempre rápido».

Más precisamente, para curiosos

Tiempo pseudopolinómico. La tabla tiene n · W celdas. n es cuántos paquetes hay, pero W es el valor de la capacidad, no cuántas cosas tiene la entrada. Si los pesos están en gramos, la caja de 50 kg pasa a ser W = 50 000 y la tabla es mil veces mayor. Si la capacidad es mil millones (bytes en un disco, céntimos en un presupuesto), la tabla no cabe en la memoria, aunque el número de paquetes sea el mismo. Un tiempo de ejecución que es un polinomio en n y en el valor de W, pero no en la longitud de W en dígitos, se llama pseudopolinómico. Cada dígito más en W multiplica el trabajo por 10. Por eso, con un W enorme y pocos paquetes, probar combinaciones con buena poda a veces es más rápido.

Memoria. La tabla entera son (n + 1) · (W + 1) números, una fila son W + 1. Pero la fila sola no dice qué paquetes: para volver atrás hacen falta todas las filas, o al menos un bit «tomado» por cada celda.

Cuando los paquetes son ilimitados. Si hay tantos de cada clase como quieras (cajas de agua de 6 kg, cada una por 4 €), «de arriba abajo» ahora es incorrecto, y «de abajo arriba» es justo lo que necesitas: cada clase puede entrar otra vez. Es el mismo bucle que en el cambio, donde cada moneda se puede usar muchas veces. El error de «Encuentra el error» es la solución correcta de otro problema.

Test

Ponte a prueba

1. ¿Qué significa la celda best[i][w] en la tabla de la mochila?La mayor tarifa que puedes obtener solo con los primeros i paquetes y una carga de como máximo w kgCuántos de los primeros i paquetes caben en w kgLa tarifa del paquete i si pesa w kg

2. La celda best[i][w] elige entre dos cosas. ¿Cuáles?El paquete i o el paquete i − 1El paquete más pesado o el más caroSin el paquete i: best[i − 1][w]. Con el paquete i: su tarifa más best[i − 1][w − su peso]

3. Los paquetes son 4 kg por 10 €, 3 kg por 7 €, 3 kg por 6 € y 1 kg por 2 €, y hay 6 kg de espacio. ¿Qué toma la regla «el más caro por kilogramo que todavía quepa»?Solo el paquete 1, 10 €Los paquetes 2 y 3, 13 €, lo mejorLos paquetes 1 y 4, 12 €, mientras que lo mejor son los paquetes 2 y 3, 13 €

4. En la tabla de una fila la capacidad va de arriba abajo. ¿Qué pasa si va de abajo arriba?best[w − peso] puede contener ya el mismo paquete, y este entra dos vecesEl programa lee fuera del arregloNada, la respuesta es la misma

5. La tabla es O(n · W). ¿Por qué eso no es «siempre rápido»?W es el valor de la capacidad, no el número de cosas. Con gramos en lugar de kilogramos la tabla se hace mil veces mayorPorque la tabla se llena dos vecesPorque n · W siempre es mayor que 2ⁿ

El problema de la mochila

Cookies