La optimización de recursos bajo restricciones es un desafío recurrente en la informática y la ingeniería. Un ejemplo paradigmático de esto es el "Problema de la Mochila" (Knapsack Problem), donde el objetivo primordial es maximizar el valor total de un conjunto de objetos seleccionados para ser transportados en un contenedor con una capacidad de peso limitada.
El Problema de la Mochila 0/1 (Versión Fundamental)
La versión 0/1 del problema de la mochila impone una restricción crucial: cada tipo de objeto solo está disponible en una única unidad. Esto significa que para cada objeto, la decisión es binaria: o se incluye completamente en la mochila (1), o no se incluye en absoluto (0). No se permite fraccionar los objetos ni incluir múltiples copias del mismo tipo.
Lógica Fundamental: ¿Incluir o Excluir? Al considerar cada objeto disponible, la estrategia de resolución se basa en un dilema simple pero potente. Para cada objeto, evaluamos dos caminos:
- No incluir el objeto: La capacidad de la mochila permanece inalterada, y el valor acumulado no se modifica. Procedemos a evaluar los objetos restantes.
- Incluir el objeto: La capacidad de la mochila disminuye (restamos el peso del objeto), y el valor total aumenta (sumamos el valor del objeto). Luego, consideramos los objetos restantes con la capacidad reducida. El desafío consiste en elegir la opción que, en cada paso, conduzca al mayor valor total posible sin exceder la capacidad máxima.
Diseño de la Tabla de Programación Dinámica (DP Table) Para abordar este problema de manera eficiente, empleamos una tabla bidimensional, matriz_dp, que registrará los resultados intermedios. Definimos matriz_dp[idx_item][cap_restante] como el valor máximo alcanzable al procesar los primeros idx_item objetos con una capacidad de mochila de cap_restante.
- El índice
idx\_itemvaría desde 0 hasta el número total de objetos. - La capacidad
cap\_restantevaría desde 0 hasta la capacidad máxima de la mochila.
Ecuación de Transición de Estados: Para el objeto actual o (con peso p_o y valor v_o), la lógica de actualización para matriz_dp[idx_item][cap_actual] es la siguiente:
- **Si la capacidad actual (
cap\_actual) es inferior al peso del objeto (p\_o):**El objetoono puede ser incluido. Por lo tanto, el valor máximo es idéntico al obtenido sin considerar este objeto:matriz\_dp\[idx\_item\]\[cap\_actual\] = matriz\_dp\[idx\_item - 1\]\[cap\_actual\]. - **Si la capacidad actual (
cap\_actual) es igual o superior al peso del objeto (p\_o):**Tenemos dos alternativas y debemos seleccionar la que ofrezca un mayor valor:
- **Opción A (No incluir
o):** El valor se mantiene igual al de la iteración anterior sin este objeto:valor\\\_sin\\\_o = matriz\\\_dp\\\[idx\\\_item - 1\\\]\\\[cap\\\_actual\\\]. - **Opción B (Incluiro):** El valor será la suma del valor del objeto actual (v\\\_o) más el valor máximo que se pudo obtener con losidx\\\_item - 1objetos anteriores y la capacidad restante (cap\\\_actual - p\\\_o):valor\\\_con\\\_o = v\\\_o + matriz\\\_dp\\\[idx\\\_item - 1\\\]\\\[cap\\\_actual - p\\\_o\\\]. El valor final es el máximo de estas dos opciones:matriz\_dp\[idx\_item\]\[cap\_actual\] = max(valor\_sin\_o, valor\_con\_o).
Implementación en Python (Matriz 2D) Esta es la implementación más directa, que mapea conceptualmente la tabla de programación dinámica.
def calcular_valor_maximo_mochila_01(pesos_items, valores_items, capacidad_limite):
"""
Determina el valor máximo de objetos que se pueden llevar en una mochila
con una capacidad limitada, donde cada objeto solo se puede usar una vez.
Args:
pesos_items (list): Lista de los pesos de cada objeto.
valores_items (list): Lista de los valores de cada objeto.
capacidad_limite (int): Capacidad máxima de la mochila.
Returns:
int: El valor máximo total de los objetos seleccionados.
"""
num_items = len(pesos_items)
# Inicializa una tabla (num_items + 1) x (capacidad_limite + 1) con ceros.
# tabla_dp[i][c] representa el valor máximo para los primeros 'i' items
# con una capacidad de 'c'.
tabla_dp = [[0] * (capacidad_limite + 1) for _ in range(num_items + 1)]
# Rellena la tabla dp
for i in range(1, num_items + 1): # Itera sobre cada item (desde el primer item real)
peso_item_actual = pesos_items[i-1] # Peso del item considerado actualmente
valor_item_actual = valores_items[i-1] # Valor del item considerado actualmente
for c in range(capacidad_limite + 1): # Itera sobre cada capacidad posible (desde 0 hasta el límite)
# Si la capacidad actual 'c' no es suficiente para el item actual
if c < peso_item_actual:
tabla_dp[i][c] = tabla_dp[i-1][c] # Se toma el valor de la fila anterior (no se incluye el item)
# Si la capacidad 'c' es suficiente, se decide si incluir o no el item
else:
# Opción 1: No incluir el item actual.
# El valor es el mismo que se obtuvo con los items anteriores y la misma capacidad.
opcion_excluir = tabla_dp[i-1][c]
# Opción 2: Incluir el item actual.
# El valor es el valor del item actual más el valor máximo
# obtenido con los items anteriores y la capacidad restante.
opcion_incluir = valor_item_actual + tabla_dp[i-1][c - peso_item_actual]
# Se elige la opción que maximiza el valor total
tabla_dp[i][c] = max(opcion_excluir, opcion_incluir)
# El resultado final se encuentra en la última celda de la tabla
return tabla_dp[num_items][capacidad_limite]
# Ejemplo de uso:
pesos_ejemplo = [1, 3, 4]
valores_ejemplo = [15, 20, 30]
capacidad_mochila = 4
print(f"Valor máximo (Mochila 0/1, 2D): {calcular_valor_maximo_mochila_01(pesos_ejemplo, valores_ejemplo, capacidad_mochila)}") # Salida esperada: 35 (item 1 y 3)
Optimización de Espacio (Arreglo 1D) Una observación clave en la ecuación de transición es que matriz_dp[idx_item][cap_actual] solo depende de los valores de la fila anterior (matriz_dp[idx_item - 1]). Esto nos permite reducir la memoria utilizada de una matriz 2D a un arreglo 1D, dp_optimizado, donde dp_optimizado[c] almacenará el valor máximo para la capacidad c.
Punto Crítico: La Dirección del Bucle Interno Para la optimización a una dimensión, el bucle que itera sobre las capacidades (c) debe recorrerse en orden descendente (de la capacidad máxima hacia el peso del objeto actual). Si el bucle fuera ascendente, al calcular dp_optimizado[c], el valor de dp_optimizado[c - peso_item_actual] ya podría haber sido actualizado con el objeto actual dentro de la misma iteración externa. Esto significaría que un objeto se podría incluir más de una vez, lo cual viola la restricción 0/1 de usar cada objeto una única vez.
def calcular_valor_maximo_mochila_01_opt(pesos_items, valores_items, capacidad_limite): """ Resuelve el problema de la mochila 0/1 con optimización de espacio (arreglo 1D). Cada objeto solo se puede incluir una vez.
Args: pesos_items (list): Lista de los pesos de cada objeto. valores_items (list): Lista de los valores de cada objeto. capacidad_limite (int): Capacidad máxima de la mochila.
Returns: int: El valor máximo total de los objetos seleccionados. """ num_items = len(pesos_items)
dp_optimizado[c] representa el valor máximo para una capacidad 'c'.
Se inicializa con ceros para todas las capacidades.
dp_optimizado = [0] * (capacidad_limite + 1)
Itera sobre cada objeto disponible
for i in range(num_items): peso_item_actual = pesos_items[i] # Peso del objeto en la iteración actual valor_item_actual = valores_items[i] # Valor del objeto en la iteración actual
Itera sobre las capacidades en orden descendente.
Esto asegura que al calcular dp_optimizado[c], el valor de dp_optimizado[c - peso_item_actual]
corresponde a la "fila anterior" (es decir, antes de considerar el objeto 'i' para esa capacidad).
for c in range(capcaidad_limite, peso_item_actual - 1, -1):
Se compara:
-
No incluir el objeto actual (el valor actual de dp_optimizado[c]). ========================================================================
-
Incluir el objeto actual (valor del objeto + valor máximo de la capacidad restante). =======================================================================================
dp_optimizado[c] = max(dp_optimizado[c], valor_item_actual + dp_optimizado[c - peso_item_actual])
return dp_optimizado[capacidad_limite]
Ejemplo de uso:
print(f"Valor máximo (Mochila 0/1, 1D optimizado): {calcular_valor_maximo_mochila_01_opt(pesos_ejemplo, valores_ejemplo, capacidad_mochila)}") # Salida esperada: 35
<h2>El Problema de la Mochila Ilimitada (Variante)</h2>
<p>A diferencia de la versión 0/1, en el Problema de la Mochila Ilimitada (o Knapsack Completo), se permite seleccionar un objeto particular múltiples veces, siempre y cuando la capacidad total de la mochila lo permita. Cada objeto es, en esencia, "infinitamente" disponible.</p>
<h3>¿Cuál es la Diferencia Clave?</h3>
<p>La distinción principal en las implementaciones optimizadas con un arreglo 1D radica en la dirección del bucle de capacidades:</p>
- **Mochila 0/1:** El bucle interno para las capacidades se ejecuta en \*\*orden descendente\*\*. Esto previene que un objeto sea reutilizado dentro de la misma iteración externa (para el mismo objeto), respetando la restricción de un uso único.
- **Mochila Ilimitada:** El bucle interno para las capacidades se ejecuta en \*\*orden ascendente\*\*. Esta dirección permite que un objeto ya considerado en la iteración externa (es decir, el `objeto\_actual`) pueda contribuir a `dp\[c - peso\_objeto\]` y luego ser añadido nuevamente para `dp\[c\]`, simulando así su selección múltiple dentro de la misma iteración del objeto.
<h3>Implementación en Python (Matriz 2D)</h3>
<p>La versión 2D para la mochila ilimitada es casi idéntica a la 0/1, con un cambio sutil pero crucial en la fórmula de transición para la opción de incluir el objeto.</p>
def calcular_valor_mochila_ilimitada(pesos_items, valores_items, capacidad_limite):
"""
Calcula el valor máximo de objetos que se pueden llevar en una mochila
con capacidad limitada, permitiendo múltiples selecciones de cada objeto.
Args:
pesos_items (list): Lista de los pesos de cada objeto.
valores_items (list): Lista de los valores de cada objeto.
capacidad_limite (int): Capacidad máxima de la mochila.
Returns:
int: El valor máximo total de los objetos seleccionados.
"""
num_items = len(pesos_items)
# Inicializa la tabla dp con ceros.
# tabla_dp[i][c] representa el valor máximo para los primeros 'i' tipos de items
# con una capacidad de 'c'.
tabla_dp = [[0] * (capacidad_limite + 1) for _ in range(num_items + 1)]
# Rellena la tabla dp
for i in range(1, num_items + 1): # Itera sobre cada tipo de item
peso_actual = pesos_items[i-1] # Peso del item actual
valor_actual = valores_items[i-1] # Valor del item actual
for c in range(capacidad_limite + 1): # Itera sobre cada capacidad posible
# Si la capacidad actual 'c' no es suficiente para el item actual
if c < peso_actual:
tabla_dp[i][c] = tabla_dp[i-1][c] # Se toma el valor de la fila anterior
# Si la capacidad 'c' es suficiente, se decide si incluir o no el item
else:
# Opción 1: No incluir el item actual.
# El valor es el mismo que se obtuvo con los tipos de items anteriores y la misma capacidad.
excluir_item = tabla_dp[i-1][c]
# Opción 2: Incluir el item actual.
# Diferencia clave: Se usa tabla_dp[i][c - peso_actual] en lugar de tabla_dp[i-1][c - peso_actual].
# Esto permite que el item actual (tipo 'i') sea potencialmente reutilizado en la capacidad restante.
incluir_item = valor_actual + tabla_dp[i][c - peso_actual]
# Se elige la opción que maximiza el valor total
tabla_dp[i][c] = max(excluir_item, incluir_item)
return tabla_dp[num_items][capacidad_limite]
# Ejemplo de uso: (los mismos datos pueden dar resultados diferentes aquí si la capacidad lo permite)
# Supongamos: pesos = [2], valores = [10], capacidad = 7.
# Mochila 0/1: 10 (solo un item de peso 2)
# Mochila Ilimitada: 30 (tres items de peso 2)
Optimización de Espacio (Arreglo 1D) La versión optimizada a 1D para la mochila ilimitada solo requiere un cambio en la dirección del bucle interno de capacidades. def calcular_valor_mochila_ilimitada_opt(pesos_items, valores_items, capacidad_limite): """ Calcula el valor máximo de objetos para una mochila con capacidad limitada, permitiendo múltiples selecciones de cada objeto, utilizando optimización de espacio (arreglo 1D).
Args: pesos_items (list): Lista de los pesos de cada objeto. valores_items (list): Lista de los valores de cada objeto. capacidad_limite (int): Capacidad máxima de la mochila.
Returns: int: El valor máximo total de los objetos seleccionados. """ num_items = len(pesos_items)
dp_opt[c] representa el valor máximo para una capacidad 'c'.
dp_opt = [0] * (capacidad_limite + 1)
Itera sobre cada tipo de objeto disponible
for i in range(num_items): peso_obj_actual = pesos_items[i] # Peso del objeto actual valor_obj_actual = valores_items[i] # Valor del objeto actual
Itera sobre las capacidades en orden ascendente (desde el peso del objeto hasta el límite).
Esto permite que el objeto actual (obj 'i') sea usado repetidamente,
ya que dp_opt[c - peso_obj_actual] ya habrá sido actualizado para incluir
potencialmente el mismo objeto 'i' en la capacidad restante para calcular c.
for c in range(peso_obj_actual, capacidad_limite + 1): dp_opt[c] = max(dp_opt[c], valor_obj_actual + dp_opt[c - peso_obj_actual])
return dp_opt[capacidad_limite]
Resumen y Comparación
Las diferencias clave entre las dos variantes del Problema de la Mochila son fundamentales para su implementación, especialmente en las versiones con optimización de espacio:
| Característica | Mochila 0/1 | Mochila Ilimitada |
|---|---|---|
| **Copias por objeto** | Una sola copia por tipo de objeto. | Múltiples copias por tipo de objeto. |
| **Lógica de inclusión** | Tomar o dejar cada objeto. | Tomar cualquier número de copias del objeto (mientras quepa). |
| **Bucle DP (1D)** | Iteración de capacidad **descendente** (de `capacidad_maxima` a `peso_objeto`). | Iteración de capacidad **ascendente** (de `peso_objeto` a `capacidad_maxima`). |
| **Efecto del bucle** | Garantiza un uso único del objeto actual por cada iteración del objeto. | Permite la inclusión repetida del objeto actual en la misma iteración del objeto. |