El fracaso no es vergonzoso, no aprender de él sí lo es.

En este artículo se exploran dos variantes especiales del problema de la mochila: la búsqueda de soluciones concretas (rutas de transferencia) y el cálculo del número de soluciones óptimas.

Antes de profundizar, es fundamental comprender dos métodos de inicialización para los arrays de programación dinámica (DP). La inicialización depende únicamente de cómo se define el array. Básicamente, existen dos enfoques:

Enfoque 1: Si dp[i][j] representa el valor máximo obtenible con los primeros i elementos y una capacidad máxima de j, entonces todo el array debe inicializarse con 0. En este caso, todas las soluciones cumplen con la restricción de capacidad (mínimo 0 y máximo infinito), por lo que el valor máximo inicial para todas es 0.

Enfoque 2: Si dp[i][j] representa el valor máximo obtenible con los primeros i elementos y una capacidad exactamente igual a j, entonces dp[0][0] debe ser 0 y el resto de los valores deben ser -infinito. La razón es que con 0 elementos, solo podemos lograr una capacidad exacta de 0 con valor 0. Todas las demás combinaciones son inválidas o no tienen sentido en este contexto, por lo que se asigna -infinito.

Búsqueda de Soluciones Concretas:

Podemos conceptualizar la programación dinámica como la búsqueda de la ruta más corta o más larga en un grafo topológico (dependiendo de la interpretación específica). En este caso, dp[n][m] representa el nodo final, y para encontrar la solución concreta, retrocedemos paso a paso desde el final.

Desde culaquier estado, hay tres posibles transiciones:

1. No se selecciona el elemento i: dp[i-1][j]
2. Se selecciona el elemento i: dp[i-1][j-v[i]] + w[i]
3. El elemento i puede ser seleccionado o no (ambas opciones conducen al mismo valor)

Para reconstruir la solución, avanzamos hacia atrás: for (i : 1 -> n) if (v[i] <= m && dp[i][m] == dp[i-1][j-v[i]] + w[i]) Seleccionar elemento i m -= v[i]

A veces, el problema requiere encontrar la solución con el orden lexicográfico mínimo. En estos casos, una técnica útil es iterar desde n hasta 1 al reconstruir la solución. Como avanzamos hacia atrás en la reconstrucción, queremos que los elementos más tempranos en la secuencia sean los más pequeños posibles. Al iterar en orden inverso, logramos este objetivo, y cuando encontramos tanto la opción 1 como la 3, las seleccionamos porque la primera opción encontrada será la lexicográficamente menor.

A continuación se presenta un ejemplo de código para resolver el problema de la mochila 0/1 con la ruta lexicográficamente mínima:

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define acelerar ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 5 
 6 const string SI = "SI";
 7 const string NO = "NO";
 8 
 9 const int MAX = 1010;
10 int tabla[MAX][MAX], volumen[MAX], valor[MAX];
11 
12 int32_t main() {
13     acelerar;
14     
15     int n, capacidad;
16     cin >> n >> capacidad;
17     for (int i = 1; i <= n; i++)
18         cin >> volumen[i] >> valor[i];
19     
20     // Rellenamos la tabla desde atrás hacia adelante
21     for (int i = n; i >= 1; i--)
22         for (int j = 0; j <= capacidad; j++) {
23             tabla[i][j] = tabla[i + 1][j];
24             if (j >= volumen[i])
25                 tabla[i][j] = max(tabla[i][j], tabla[i + 1][j - volumen[i]] + valor[i]);
26         }
27     
28     int espacio_restante = capacidad;
29     for (int i = 1; i <= n; i++)
30         if (volumen[i] <= espacio_restante && 
31             tabla[i][espacio_restante] == tabla[i + 1][espacio_restante - volumen[i]] + valor[i]) {
32             cout << i << ' ';
33             espacio_restante -= volumen[i];
34         }
35     return 0;
36 }

Construcción de Solución Concreta*Cálculo del Número de Soluciones Óptimas:

Para esta variante, necesitamos un array adicional g[i][j] que registre el número de rutas que alcanzan exactamente el estado dp[i][j]. En este caso, es preferible definir dp[i][j] como el valor máximo con capacidad exactamente igual a j, por lo que se inicializa con -infinito.

Al igual que antes, existen tres casos para llegar a un estado:

1. No se selecciona el elemento i: dp[i-1][j], y g[i][j] += g[i-1][j]
2. Se selecciona el elemento i: dp[i-1][j-v[i]] + w[i], y g[i][j] += g[i-1][j-v[i]]
3. Ambas opciones son válidas: g[i][j] += g[i-1][j] + g[i-1][j-v[i]]

La definición de "capacidad exacta" es crucial aquí. Si no usáramos esta restricción, contaríamos rutas duplicadas y necesitaríamos aplicar el principio de inclusión-exclusión. Con la definición de capacidad exacta, este problema se evita.

Al final, para obtener el número total de soluciones óptimas, debemos verificar qué estados alcanzan el valor máximo. Para cada estado dp[i][j] que coincida con el valor óptimo, sumamos g[i][j] al resultado. Es importante recordar que, debido a nuestra definición, dp[n][m] podría no ser el valor óptimo global, por lo que debemos buscar el valor máximo en toda la tabla.

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define acelerar ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 5 
 6 const string SI = "SI";
 7 const string NO = "NO";
 8 
 9 const int MAX = 1010, MOD = 1e9 + 7;
10 int dp[MAX], caminos[MAX], tamano[MAX], beneficio[MAX];
11 
12 int32_t main() {
13     acelerar;
14     
15     int n, capacidad_max;
16     cin >> n >> capacidad_max;
17     for (int i = 1; i <= n; i++)
18         cin >> tamano[i] >> beneficio[i];
19     
20     // Inicialización con valores mínimos
21     memset(dp, 0x8f, sizeof dp);
22     dp[0] = 0;
23     caminos[0] = 1;
24     
25     // Procesamiento de elementos
26     for (int i = 1; i <= n; i++)
27         for (int j = capacidad_max; j >= tamano[i]; j--) {
28             int maximo = max(dp[j], dp[j - tamano[i]] + beneficio[i]);
29             int contador = 0;
30             
31             if (maximo == dp[j])
32                 contador = (contador + caminos[j]) % MOD;
33             if (maximo == dp[j - tamano[i]] + beneficio[i])
34                 contador = (contador + caminos[j - tamano[i]]) % MOD;
35                 
36             dp[j] = maximo;
37             caminos[j] = contador % MOD;
38         } 
39 
40     // Encontrar el valor máximo
41     int mejor_valor = 0;
42     for (int j = 0; j <= capacidad_max; j++) 
43         if (dp[j] > dp[mejor_valor])
44             mejor_valor = j;
45     
46     // Contar todas las soluciones óptimas
47     int total_soluciones = 0;
48     for (int j = 0; j <= capacidad_max; j++)
49         if (dp[j] == dp[mejor_valor])
50             total_soluciones = (total_soluciones + caminos[j]) % MOD;
51             
52     cout << total_soluciones << '\n';
53     return 0;
54 }

Conteo de Soluciones Óptimas Basado en conceptos del "Curso Completo sobre Problemas de Mochila"