Calculadora Knapsack 0/1 (Problema de la Mochila)

Calculadora problema de la mochila 0/1, fraccional y bounded: programacion dinámica, greedy, comparacion eficiencia valor/peso y reconstruccion de la solución.

Parámetros de cálculo
¿Te ha sido útil esta calculadora?

El problema de la mochila

El problema de la mochila (knapsack) es uno de los 21 problemas NP-completos originales de Karp (1972) y piedra angular de la optimización combinatoria. Dada una colección de objetos con peso y valor, y una mochila de capacidad W, determinar el subconjunto que maximiza el valor total sin exceder la capacidad. Variantes principales: 0/1 (objeto entero o excluido), fraccional (fracciones permitidas), bounded (copias limitadas).

Formulación matemática

Maximizar Sigma v_i * x_i sujeto a Sigma w_i * x_i <= W. Con x_i en {0,1} para 0/1, x_i en [0,1] para fraccional, x_i en {0,1,...,q_i} para bounded. La versión de decisión es NP-completa; la optimización es NP-hard. Existen algoritmos pseudo-polinomiales O(nW) via programación dinámica.

Programación dinámica

El algoritmo clasico construye dp[i][w] = valor máximo con los primeros i objetos y capacidad w. Recurrencia: dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i) si w_i <= w. Caso base dp[0][w] = 0. La solución óptima es dp[n][W]; los objetos se recuperan por backtracking. Complejidad O(nW) tiempo, reducible a O(W) espacio.

Las cuatro modalidades

  1. Resolver 0/1: programación dinámica con reconstrucción.
  2. Fraccional: greedy ordenando por v/w decreciente.
  3. Bounded: descomposición binaria reduciendo a 0/1.
  4. Comparación eficiencia: rapports valor/peso.

Greedy falla en 0/1

Ordenar por v/w decreciente resuelve el fraccional pero puede ser arbitrariamente subóptimo para 0/1. Ejemplo: W=10, objetos [(6,60), (5,50), (5,50)]. Greedy elige el primero (ratio 10) dejando W=4 sin usar: valor 60. El óptimo toma los ultimos dos: valor 100.

Aproximación FPTAS

Existe un esquema de aproximación totalmente polinomico (FPTAS) para knapsack 0/1: para todo epsilon>0, algoritmo en O(n^3/epsilon) que devuelve solución >= (1-epsilon) * OPT. Se obtiene escalando valores por v_max*epsilon/n y aplicando DP sobre valores.

Ejemplo clasico

W=10, objetos (2,3), (3,4), (4,5), (5,6). DP da dp[4][10] = 13 seleccionando objetos 1, 2, 4 (pesos 2+3+5=10, valores 3+4+6=13).

Aplicaciones

  • Asignación de presupuesto: selección de proyectos con ROI máximo.
  • Cutting stock: optimización de corte en textil, papel, metal.
  • Optimización de portafolio: selección de activos con limite de capital.
  • Carga de contenedores: logistica maritima y aerea.
  • Asignación de recursos en cloud: VM placement con limites RAM/CPU.

Historia del problema de la mochila

El problema de la mochila (en inglés knapsack) toma su nombre de la situación intuitiva de quien debe llenar una mochila de capacidad limitada eligiendo, entre muchos objetos, los de valor total máximo. Formalizado en la investigación operativa a mediados del siglo XX, se convirtió en uno de los problemas más estudiados de la informática teórica. En 1972 Richard Karp lo incluyó en su célebre lista de 21 problemas NP-completos, sellando su dificultad intrínseca. El problema tuvo también un papel histórico en criptografía: en 1978 Ralph Merkle y Martin Hellman propusieron uno de los primeros criptosistemas de clave pública basados en la mochila (el Merkle-Hellman knapsack). La idea era usar la dificultad del problema como garantía de seguridad, pero el sistema fue espectacularmente roto por Adi Shamir en 1982, que aprovechó su estructura particular. Desde entonces la mochila sigue siendo un banco de pruebas fundamental para algoritmos exactos, heurísticos y de aproximación.

Por qué el algoritmo es pseudo-polinomial

La programación dinámica resuelve la mochila 0/1 en tiempo O(n·W), donde n es el número de objetos y W la capacidad. A primera vista parece eficiente, pero hay un detalle sutil: W es un valor numérico, no el tamaño de la entrada. Para representar la capacidad W bastan unos log₂(W) bits, así que el tiempo O(n·W) es exponencial en la longitud de los datos de entrada. Esto es lo que se entiende por algoritmo pseudo-polinomial: polinomial en el valor de los números, pero exponencial en el número de cifras. Por eso la mochila es NP-hard en sentido débil: si las capacidades y pesos son pequeños, la DP es rapidísima, pero con números enormes (cientos de cifras) se vuelve impracticable. Un algoritmo realmente polinomial en el tamaño de la entrada no se conoce, y su existencia equivaldría a demostrar P = NP.

Actualizado a julio de 2026

Preguntas frecuentes

¿Por qué knapsack 0/1 es NP-hard si DP es O(nW)?

Porque O(n·W) es pseudo-polinomial, no polinomial. W es un valor numérico que se representa con unos log₂(W) bits, así que respecto a la longitud real de la entrada el tiempo es exponencial. Con pesos y capacidades pequeños la DP es rapidísima, pero si los números tienen cientos de cifras se vuelve impracticable. La NP-hardness de la mochila es débil precisamente porque está ligada a la magnitud de los números, no al número de objetos.

¿Cuándo usar DP y cuándo greedy?

La programación dinámica da la solución exacta óptima del problema 0/1, pero cuesta O(n·W): conviene cuando la capacidad es moderada. El enfoque greedy por valor/peso es rapidísimo (O(n log n)) pero da el óptimo solo para la mochila fraccionaria, donde los objetos son divisibles. En el problema 0/1 el greedy puede equivocarse mucho. Se usa el greedy solo para estimaciones rápidas o como heurística de partida.

¿Cómo funciona la descomposición binaria para bounded?

En el problema bounded cada objeto tiene una cantidad máxima disponible. En vez de duplicarlo muchas veces, se descompone en grupos de tamaño 1, 2, 4, 8, ... (potencias de dos), más un resto. Con estos paquetes se puede componer cualquier cantidad hasta el máximo, y el problema se reduce a una mochila 0/1 con log(Qmax) objetos extra por artículo. Así el coste baja de O(n·W·Qmax) a O(n·W·log Qmax), una ganancia enorme.

¿Existe un algoritmo mejor que O(nW)?

Para el caso general no se conoce un algoritmo polinomial en el tamaño de la entrada, y encontrarlo demostraría P = NP. Existen sin embargo esquemas de aproximación completamente polinomiales (FPTAS) que, aceptando un pequeño error relativo ε, garantizan una solución dentro de (1−ε) del óptimo en tiempo polinomial en n y 1/ε. En la práctica se usan también algoritmos branch-and-bound que, con cotas superiores, resuelven instancias grandes mucho más rápido que el peor caso.

¿El knapsack multidimensional es mucho más difícil?

Sí. En el knapsack multidimensional cada objeto tiene varios atributos de coste (peso, volumen, etc.) y hay varias restricciones de capacidad que respetar simultáneamente. La programación dinámica requeriría una tabla con una dimensión por restricción, disparando memoria y tiempo. El problema sigue siendo NP-hard y ya no admite un FPTAS simple: en la práctica se aborda con programación lineal entera, metaheurísticas o algoritmos branch-and-bound sofisticados.

¿Cómo tratar objetos divisibles en la práctica?

Si los objetos son divisibles se pasa a la mochila fraccionaria, que se resuelve de forma óptima con un simple greedy: se ordenan los objetos por razón valor/peso decreciente y se llena la mochila empezando por los más eficientes, tomando una fracción del último para saturar exactamente la capacidad. Es el caso típico de materiales continuos como líquidos, polvos o metales preciosos fundibles, y a diferencia del caso 0/1 el greedy es aquí rigurosamente óptimo.

¿Knapsack se reduce a SUBSET-SUM?

SUBSET-SUM es un caso particular de la mochila en el que el valor de cada objeto es igual a su peso y se pregunta si existe un subconjunto que alcanza exactamente la capacidad. Es a su vez NP-completo, y su reducción a la mochila muestra la dificultad de esta última. Ambos comparten la misma estructura pseudo-polinomial: la DP sobre SUBSET-SUM cuesta O(n·S), donde S es la suma objetivo, con el mismo límite de aplicabilidad que la mochila.

¿Para qué sirve el problema de la mochila en la práctica?

Está en todas partes en los problemas de asignación óptima de recursos limitados: en la selección de inversiones con presupuesto fijo (capital budgeting), en el corte de materiales para minimizar desperdicios, en la carga de contenedores y aviones, en la planificación de la producción y en la selección de proyectos. Aparece también en la criptografía histórica, en la gestión de memoria y en los sistemas de recomendación, donde haya que maximizar un valor respetando una restricción de capacidad.

Comentarios (0)

Sin comentarios aún. ¡Sé el primero!