Introducción al Algoritmo de la Mochila (Knapsack)

• ¿Qué es el Algoritmo de la Mochila?
• Casos de Uso
• Comparativa de Algoritmos para el Problema de la Mochila
• Ejemplos Reales de Algoritmo de la Mochila en JavaScript
• Ejemplo 1: Organizar elementos en una caja que soporta máximo 2 kilos
• Ejemplo 2: Selección de inversiones
• Ejemplo 3: Selección de inversiones

El algoritmo de la mochila es un enfoque clásico en la teoría de la optimización combinatoria y es fundamental en muchos campos de la informática y la investigación operativa. El problema de la mochila, conocido en inglés como Knapsack problem, involucra una serie de elementos, cada uno con un peso y un valor, y una mochila con una capacidad de peso máxima. El objetivo es determinar la cantidad de cada elemento a incluir en la mochila de manera que se maximice el valor total sin exceder la capacidad máxima.

La historia del algoritmo de la mochila se remonta a la década de 1950, cuando T.C. Hu y otros investigadores comenzaron a estudiar problemas de optimización relacionados con la asignación de recursos limitados. Sin embargo, el problema de la mochila se ha documentado de forma aún más antigua en problemas económicos y militares, como la asignación de raciones o la carga de barcos con mercancías. La formalización matemática moderna del problema se debe en gran parte a P.C. Gilmore y R.E. Gomory, quienes a lo largo de la década de los 60 introdujeron métodos específicos para resolver variantes de este problema.

¿Qué es el Algoritmo de la Mochila?

Imagina que tienes una mochila y quieres llevar ciertos juguetes contigo para un viaje. Cada juguete tiene un peso (qué tan pesado es) y un valor (qué tanto te gusta). Pero, la mochila solo puede cargar hasta cierto peso máximo, ¡no puedes llevar todo lo que quieres!

El objetivo es elegir los juguetes de tal manera que el valor total (el cuánto te gustan) sea lo más alto posible, pero sin exceder el peso que la mochila puede cargar. Aquí, el 'peso' significa cuánto pesa cada juguete, y el 'valor' significa cuánto te gusta cada juguete.

• Peso: Cuánto pesa cada juguete.
• Valor: Qué tanto te gusta cada juguete.

Por ejemplo, si tienes una mochila que puede llevar 5 kilos y tienes un oso de peluche que pesa 3 kilos y te gusta mucho, y una pelota que pesa 2 kilos y también te gusta mucho, puedes llevar ambos en la mochila. Pero si tienes también un robot que pesa 5 kilos, no podrías llevar nada más con el robot porque la mochila no lo soportaría.

El 'algoritmo de la mochila' ayuda a decidir cuáles juguetes llevar para que te diviertas más en tu viaje sin que la mochila se rompa por llevar demasiado peso.

Casos de Uso

• Selección de inversiones: Maximizar el rendimiento de una cartera de inversiones dadas ciertas restricciones de capital.
• Planificación de la producción: Determinar la cantidad óptima de productos que se deben fabricar para maximizar ganancias.
• Compresión de datos: Elegir los datos a almacenar en un dispositivo limitado por capacidad.
• Selección de proyectos: Priorizar proyectos en función de sus beneficios y restricciones de recursos.

Comparativa de Algoritmos para el Problema de la Mochila

Ejemplos Reales de Algoritmo de la Mochila en JavaScript

Ejemplo 1: Organizar elementos en una caja que soporta máximo 2 kilos

Supongamos que tenemos una caja que puede soportar un máximo de 2 kg. Tenemos varios elementos, cada uno con un peso y un valor asociados. Queremos maximizar el valor total de los elementos en la caja sin exceder los 2 kg.

// Definimos los elementos con sus pesos y valores
const items = [
  { weight: 1, value: 1 },
  { weight: 2, value: 2 },
  { weight: 1, value: 3 },
  { weight: 1.5, value: 1 },
];

// Capacidad máxima de la caja
const maxWeight = 2;

const knapsack = (items, maxWeight) => {
  const n = items.length;
  const dp = Array(n + 1).fill().map(() => Array(maxWeight * 10 + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const { weight, value } = items[i - 1];
    for (let w = 0; w <= maxWeight * 10; w++) {
      if (weight * 10 <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight * 10] + value);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][maxWeight * 10];
};

console.log(`El valor máximo que se puede llevar en la caja es: ${knapsack(items, maxWeight)}`);

El código anterior define una función knapsack que utiliza un enfoque dinámico para resolver el problema de la mochila. Usamos una matriz dp para rastrear el valor máximo posible para cada peso hasta el máximo permitido (2 kg en este caso).

Ejemplo 2: Selección de inversiones

Supongamos que queremos maximizar el rendimiento de una cartera de inversiones. Cada inversión tiene asociado un costo y un rendimiento esperado. Queremos maximizar el rendimiento total sin exceder un presupuesto dado.

// Definimos las inversiones con sus costos y rendimientos
const investments = [
  { cost: 100, return: 200 },
  { cost: 200, return: 300 },
  { cost: 150, return: 400 },
  { cost: 120, return: 160 },
];

// Capital disponible
const capital = 250;

const knapsack = (investments, capital) => {
  const n = investments.length;
  const dp = Array(n + 1).fill().map(() => Array(capital + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const { cost, return: ret } = investments[i - 1];
    for (let c = 0; c <= capital; c++) {
      if (cost <= c) {
        dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - cost] + ret);
      } else {
        dp[i][c] = dp[i - 1][c];
      }
    }
  }
  return dp[n][capital];
};

console.log(`El rendimiento máximo que se puede obtener es: ${knapsack(investments, capital)}`);

El código anterior utiliza el mismo enfoque dinámico que el ejemplo anterior, adaptado para las inversiones. La matriz dp rastrea el rendimiento máximo posible para cada cantidad de capital hasta el límite disponible.

Estos son ejemplos con fines de entender como funciona el algoritmo de la mochila, puedes estudiarlos y modificarlos según tus necesidades. Ejemplo: Para devolver los items que cumplen la condición. 

Ejemplo 3: Selección de inversiones

Tomaremos como base el ejemplo 2 de las inversiones, pero en este caso queremos que nos retorne cuales son las inversiones que debemos hacer para un máximo retorno, el código seria el siguiente. 

// Definimos las inversiones con sus costos y rendimientos
const investments = [
  { cost: 100, return: 200 },
  { cost: 200, return: 300 },
  { cost: 150, return: 400 },
  { cost: 120, return: 160 },
];

// Capital disponible
const capital = 250;

const knapsack = (investments, capital) => {
  const n = investments.length;
  const dp = Array(n + 1).fill().map(() => Array(capital + 1).fill(0));
  const selected = Array(n + 1).fill().map(() => Array(capital + 1).fill(false));

  for (let i = 1; i <= n; i++) {
    const { cost, return: ret } = investments[i - 1];
    for (let c = 0; c <= capital; c++) {
      if (cost <= c) {
        if (dp[i - 1][c - cost] + ret > dp[i - 1][c]) {
          dp[i][c] = dp[i - 1][c - cost] + ret;
          selected[i][c] = true;
        } else {
          dp[i][c] = dp[i - 1][c];
        }
      } else {
        dp[i][c] = dp[i - 1][c];
      }
    }
  }

  let res = dp[n][capital];
  let w = capital;
  const itemsSelected = [];

  for (let i = n; i > 0 && res > 0; i--) {
    if (selected[i][w]) {
      itemsSelected.push(investments[i - 1]);
      w -= investments[i - 1].cost;
      res -= investments[i - 1].return;
    }
  }

  return itemsSelected;
};

console.log(`Las inversiones seleccionadas para maximizar el rendimiento son:`, knapsack(investments, capital));

El código anterior utiliza el mismo enfoque dinámico que el ejemplo 2, adaptado para las inversiones. La matriz dp rastrea el rendimiento máximo posible para cada cantidad de capital hasta el límite disponible. Además, se utiliza otra matriz llamada selected para rastrear las inversiones seleccionadas que permiten alcanzar ese rendimiento máximo.

Al final, se reconstruye la lista de inversiones desde la matriz selected y se devuelven las inversiones que se deben hacer para obtener el máximo rendimiento posible.

Espero que con este tutorial quede un poco mas claro como usar este algoritmo, y si no lo conocías ya tienes nuevos conocimientos para usar en tus proyectos.