Solución del problema de la mochila 0/1 mediante un ejemplo de programación dinámica

¿Qué es el problema de la mochila?

El Problema de la mochila es un problema clásico de optimización combinatoria. Un supermercado n paquetes (n ≤ 100). Paquete i Un ladrón no puede transportar un peso que exceda la capacidad M (M ≤ 100). ¿Qué paquetes debería llevarse para maximizar el valor total?

Entrada:

• Peso máximo M y número de bultos n.
• Matriz de pesos W[i] y valor correspondiente V[i].

Salida:

• Valor total máximo que se puede obtener dentro de la capacidad.
• El conjunto exacto de paquetes que el ladrón debería llevarse.

El algoritmo de la mochila se divide en dos variantes bien conocidas:

• 0/1 Problema de la mochila Resuelto mediante programación dinámica. Cada paquete se toma completo o se deja atrás; no hay partes fraccionadas ni duplicados.
• Problema de mochila fraccionada Se resuelve mediante una estrategia voraz. Aquí puedes tomar una fracción de cualquier paquete para completar la capacidad restante.

Cómo resolver el problema de la mochila usando programación dinámica con ejemplo

El método de divide y vencerás divide un problema grande en subproblemas y continúa dividiéndolos hasta que cada subproblema sea fácil. Sin embargo, la recursión simple a menudo resuelve el mismo subproblema muchas veces y desperdicia trabajo.

La idea central de la programación dinámica de la mochila es almacenar cada subproblema resuelto en una tabla. Las llamadas repetidas leen la respuesta en lugar de recalcularla, lo que convierte una recursión exponencial en código de tiempo polinomial.

Resuelva el problema de la mochila mediante programación dinámica

Para diseñar una solución de Programación Dinámica, siga cuatro pasos:

• Resuelve primero los subproblemas más pequeños.
• Derive una relación de recurrencia que construya la solución de un subproblema a partir de otros más pequeños.
• Almacenar las respuestas de los subproblemas en una tabla calculada de abajo hacia arriba utilizando la recurrencia.
• Elabore la respuesta final a partir de la tabla completamente rellenada.

Analizar el problema de la mochila 0/1

El valor óptimo depende de dos factores independientes:

1. ¿Cuántos paquetes se están considerando todavía?
2. El peso restante que la mochila aún puede soportar.

Dado que la función objetivo depende de dos cantidades, la tabla de opciones debe ser bidimensional. Sea B[i][j] denota el valor máximo al elegir entre paquetes {1, …, i} con límite de peso j.

• La respuesta final es B[n][M], el mejor valor total en todos los n paquetes con capacidad M.
• El peso total seleccionado siempre está limitado por la capacidad actual: B[i][j] ≤ j.

Ejemplo: si B[4][10] = 8, el mejor peso total de los primeros cuatro paquetes con capacidad 10 es 8. Algunos de esos cuatro paquetes pueden omitirse.

Fórmula para calcular B[i][j]

• W[i], V[i] son el peso y el valor del paquete i, donde i está en {1, …, n}.
• M es el peso máximo que puede soportar la mochila.

Caso base con un paquete: para cada capacidad j ≥ W[1]:

B[1][j] = W[1]

En el caso general, decida si incluir el paquete i bajo la capacidad j:

• Si el paquete i es salteado, B[i][j] es igual al mejor valor utilizando los paquetes {1, …, i-1} bajo la capacidad j:

B[i][j] = B[i - 1][j]

• Si el paquete i es adoptado (permitido solo cuando W[i] ≤ j), B[i][j] es igual a V[i] más el mejor valor de los paquetes {1, …, i-1} bajo la capacidad j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Elige el mayor de los dos candidatos.

Bases de la programación dinámica

La combinación de ambos casos da como resultado la recurrencia completa:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

El caso base es B[0][j] = 0 para cada j, porque los paquetes cero dan un valor cero independientemente de la capacidad.

Calcular la tabla de opciones

Construye B usando la recurrencia. Una vez que B esté lleno, la misma tabla controla el trace-back que reconstruye los paquetes elegidos. La tabla B tiene n + 1 filas y M + 1 columnas:

• La fila 0 es el caso base, rellena de ceros.
• Utilice la fila 0 para calcular la fila 1, la fila 1 para calcular la fila 2, y continúe hasta que se complete la fila n.

Tabla de opciones

Trace

Una vez que B esté completo, concéntrese en B[n][M], el valor total óptimo en todos los n paquetes con capacidad M.

• If B[n][M] = B[n-1][M]El paquete n no fue seleccionado, así que continúe. tracing de B[n-1][M].
• If B[n][M] ≠ B[n-1][M]Se seleccionó el paquete n, así que continúe tracing de B[n-1][M – W[n]].

Repita el proceso hasta llegar a la fila 0 de la tabla.

Algoritmo para consultar la tabla de opciones para encontrar los paquetes seleccionados

Nota: siempre que B[i][j] = B[i-1][j], el paquete i no está seleccionado. El valor B[n][M] es el valor total óptimo que se puede guardar en la mochila.

Pasos para tracseleccionando los paquetes elegidos:

• Paso 1: Comience en i = n, j = M.
• Paso 2: Escanee la columna j de abajo hacia arriba hasta encontrar una fila i donde B[i][j] > B[i-1][j]. Marque el paquete i como seleccionado: Select[i] = true.
• Paso 3: Actualizar j = j – W[i]. Si j > 0, volver al paso 2; de lo contrario, ir al paso 4.
• Paso 4: Imprime todos los paquetes marcados como seleccionados.

Java Code

Las siguientes Java El método llena B[][] de abajo hacia arriba, imprime la tabla para su inspección y luego traces los paquetes seleccionados.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Función mochilaDyProg() en Java

Explicación del código:

1. Asignar tabla B[][] y inicializar cada celda a 0.
2. Rellene B[][] de abajo hacia arriba utilizando la recurrencia de la sección anterior.
3. Comience cada celda con el valor "skip package i". B[i-1][j].
4. Si seleccionar el paquete i es factible y proporciona un valor estrictamente mejor, sobrescriba la celda.
5. Trace los elementos seleccionados de la fila n de vuelta a la fila 0.
6. Siempre que se elija el paquete n, disminuya la capacidad restante en W[n-1].

Nota de corrección: el fragmento original modificó el parámetro M mientras aún leo B[n][M]La versión más segura anterior utiliza un cursor separado. j para la trace.

El Java El controlador ejecuta el algoritmo en dos ejemplos resueltos:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Resultado del primer ejemplo:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Resultado para el segundo ejemplo:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Complejidad temporal y espacial del problema de la mochila 0/1

• Complejidad temporal: O(n · M) — los dos bucles anidados recorren n elementos a través de M+1 estados de capacidad.
• Complejidad espacial: O(n · M) para la tabla completa, reducible a O(M) mediante keeping solo la fila anterior cuando tracNo es necesario el reembolso electrónico.

El tiempo de ejecución es pseudopolinomio: polinomial en el valor de M pero exponencial en los bits utilizados para codificar M. Por eso el problema de la mochila 0/1 sigue siendo NP-difícil, aunque la programación dinámica sea eficiente en la práctica.

Aplicaciones del problema de la mochila 0/1

• Carga de mercancías, embalaje de contenedores y preparación de pedidos en almacén con límites de peso.
• Asignación presupuestaria entre proyectos de inversión con coste fijo y rentabilidad prevista.
• Problemas de corte en la fabricación que impiden la separación de piezas individuales.
• Esquemas criptográficos como Merkle-Hellman que se basan en la dificultad del problema de la mochila.
• Planificación con recursos limitados en la computación en la nube y asignación de tareas a la CPU.
• Selección de características en aprendizaje automático con un presupuesto fijo de características.

Preguntas Frecuentes