CAPÍTULO 3

EL PROBLEMA DE LA MOCHILA

47
3.1 Introducción

El Problema de la Mochila es un problema simple de entender: hay una persona que tiene una
mochila con una cierta capacidad y tiene que elegir que elementos ubicará en ella. Cada uno de los
elementos tiene un peso y aporta un beneficio. El objetivo de la persona es elegir los elementos que
le permitan maximizar el beneficio sin excederse de la capacidad permitida.

A la vez es un problema complejo, si por complejidad nos referimos a la computacional. Un prob-

lema se cataloga como inherentemente difícil si su solución requiere de una cantidad significativa de
recursos computacionales, sin importar el algoritmo utilizado. El Problema de la Mochila forma parte
de una lista histórica de problemas NP-Completos elaborada por Richard Karp en 1972.

En el caso del Problema de la Mochila, si contáramos con 4 productos, para saber cuál es la mejor
solución podríamos probar las 24 = 16 posibilidades. El 2 se desprende del hecho de que cada
decisión es incluir o no al producto y el 4 de la cantidad de productos. 16 posibilidades es un número
manejable, sin embargo, si la cantidad de elementos por ejemplo ascendiera a 20, tendríamos que
analizar nada más y nada menos que 220 = 1048576 posibilidades.

Como parte de la aplicación del Problema de la Mochila como una forma de emular situaciones
reales donde es necesario acomodar artículos de diferentes dimensiones en un espacio reducido. Se
puede emplear, como ejemplo, el uso de contenedores en las aduanas, donde se requiere enviar ítems
de diferentes pesos, tamaños y valores de beneficio. Por otra parte, en la misma aduana, es necesario
almacenar, de manera temporánea, los contenedores mismos, por lo que este problema puede ser
resuelto con base en la soluciones propuesta para el problema de la mochila.

En aspectos de criptografía, en el caso de descifrar contraseñas, este problema se puede ver como un
número de contenedores que pueden tener n valores cada uno. En otro sentido, cuando es necesario
traducir un texto encriptado, en el momento de identificar los espacios, cada palabra puede fungir
como un contenedor de ni ítems (caracteres de la palabra), donde cada caracter i puede tener n
posibles artículos.

Como parte de la aplicación del Problema de la Mochila, y haciendo una revisión de la literatura
actual se pueden resolver problemas relacionados con:

• La selección de proyectos, donde cada proyecto se puede ver como un contenedor de diferentes
tales como: personas, recursos, etc.

48
 • En la solución de problemáticas donde es necesario detectar patrones de corte.

• En situaciones donde se evidencia problemas de distribución de carga (física, eléctrica, etc.).

• Cuando se requiere abastecer vehículos de transporte y entrega de productos de diferentes

tamaños que deben ser colocados en múltiples compartimentos de igual o diferente tamaño.

• Asignación de procesadores y datos en sistemas distribuidos.

El Problema de la Mochila se puede resolver por medio de diferentes técnicas, métodos exactos,
heurísticos y metaheurísticos. Por ejemplo, mediante el uso de la Programación Dinámica, en donde
generalmente se emplean cuatro tipos de visualización: árbol de recursión, grafo de dependencia,
tabla de valores y tabla de decisiones. También se pueden usar los denominados algoritmos voraces,
con los cuales no siempre es posible dar una solución óptima al problema, sin embargo es posible
obtener aproximaciones muy buenas en tiempo razonable. Así mismo se ha implementado una gran
variedad de metaheurísticas, entre ellas, metaheurísticas parametrizadas, mediante la combinación de
parámetros.

Es importante señalar que existen variantes para el Problema de la Mochila, entre los cuales podemos
encontrar:

• Problema de la Mochila 0-1: cuando existe 1 solo objeto por cada tipo.

• Problema de la Mochila no Acotado: Cuando algún tipo contiene un número infinito de objetos.

• Problema de la Mochila de Múltiple Elección: Cuando estamos ante la presencia de un Prob-

lema de Mochila 0-1, donde los objetos están subdivididos en clases, y solamente podemos
seleccionar un objeto de cada clase.

• Problema de la Mochila Múltiple: cuando en un Problema de Mochila 0-1 se tiene más de una
mochila, cada una con su capacidad.

En este apartado se trabajará sobre un tipo de Problema de Mochila 0-1, específicamente el

perteneciente a la familia de los problemas de Programación Entera, donde los objetos del conjunto
no se repiten y no se puede partir.

49
3.2 Formulación Matemática del Problema de la Mochila

Supongamos que estamos planeando un viaje de senderismo;

y estamos, por lo tanto, interesados en llenar una mochila
con los elementos que se consideran necesarios para el vi-
aje. Hay n diferentes tipos de elementos que se consideran
deseables; estos podrían incluir una botella de agua, man-
zana, naranja, sándwich, etc. adelante. Cada tipo de ele-
mento tiene un conjunto dado de dos atributos, es decir,
un peso (o volumen) y un valor que cuantifica el nivel de Figura 3.1: Problema de la
importancia asociado con cada unidad de ese tipo de ele- Mochila
mento.

Dado que la mochila tiene un peso (o volumen) limitado por su capacidad, el problema de interés
consiste en averiguar cómo cargar la mochila con una combinación de unidades de los tipos
especificados de elementos que se obtiene el mayor valor total. Lo que acabamos de describir se
conoce como el problema de la mochila.

Una gran variedad de problemas de asignación de recursos se puede convertir en el marco deL
Problema de la Mochila. La idea general es pensar en la capacidad de la mochila como la cantidad
disponible de un recurso y los tipos de elementos como las actividades a las que este recurso puede
ser asignado. Dos ejemplos rápidos son la asignación de un presupuesto de publicidad para las
promociones del individuo productos y la asignación de su esfuerzo a la preparación de los exámenes
finales en diferentes asignaturas.

Los datos del problema se pueden expresar en términos matemáticos de la siguiente manera:

• Los objetos están numerados por el índice i variando de 1 a n .

• Los números wi y pi representan el peso y el valor del número i .

• La capacidad de la mochila se denomina en esta fórmula W .

Existen muchas manera de llenar la mochila, para decidir a cada uno de ellos debemos de decir para
cada objeto si lo metemos a la mochila o no, pudiendo utilizar el código binario que cuando xi = 1 ,
metemos el objeto a la mochila, o xi = 0 , se pone afuera, y para ir llenando esta mochila podemos

50
utilizar un vector de contenido, que comprende: X = (x1 , x2 , ..., xn ), entonces podemos expresar
una función del contenido del vector.

Para un contenido dado X , el valor total de la bolsa es:

n
X
Z(x) = x i pi
i=1

De la misma manera, la suma de los pesos de los objetos es:

n
X
W (x) = xi w i
i=1

El problema entonces lo podemos enunciar como un contenido de vectores X = (x1 , x2 , ..., xn ), que
tienen componentes de ceros y unos, teniendo como máximo la restricción de la función Z(x).

n
X
W (x) = xi w i ≤ W
i=1

Esto quiere decir que la suma de los pesos (o sea, la función W (x) ), de los objetos que pusimos en
la mochila no deben de superar la capacidad de esta, (o sea, la W ). Podemos decir que:

• Z(x) es una función objetivo (como su nombre lo dice, representa el objetivo del problema,
esta expresión se maximiza o se minimiza.

• Un vector X que cumple con la restricción W en la tercera fórmula se le nombra factible (o

sea, que se pude hacer).

• Si tenemos un resultado máximo en Z(x), entonces X es óptimo.

• Se le pueden agregar otras restricciones según tengamos un caso, en esta liga, encontramos
diferentes casos singulares.

Con esto podemos argumentar que tenemos un problema de decisión cuando para decidir a cada uno
de ellos debemos de decir para cada objeto si lo metemos a la mochila o no, que cuando xi = 1 ,
metemos el objeto a la mochila, o xi = 0, se pone afuera y podemos decir que es un problema de
optimización porque podemos encontrar funciones objetivo, valores óptimos utilizando las declara-
ciones matemáticas.

51
3.3 Tratamiento metodológico

El tratamiento metodológico que se realizará con el Problema de la Mochila es el siguiente: primero

se resolverán ciertos problemas de baja dimensión, mediantes diferentes métodos; para iniciar
se utilizará un algoritmo exacto (búsqueda exhaustiva), después un algoritmo de Programación
Dinámica, seguidamente se propone encontrar la solución con un algoritmo heurístico y luego se
confirmarán los resultados obtenidos con la aplicación de un herramienta computacional como lo es
el WinQsb.

Ejemplo 3.1 . Un turista nacional planea salir el fin de semana a la Isla de Ometepe. Hay cuatro
artículos que desea llevar consigo, pero entre todos sobrepasan las 5 kilogramos que considera puede
cargar.

El peso y valor de cada artículo se muestran en la siguiente tabla

artículo 1 2 3 4
Peso 2 3 4 5
Valor 3 4 5 6

Tabla 3.1: Datos ejemplo 3.1

¿Qué artículos tendría que llevar para que el valor de la mochila sea máximo?

Solución 1: (Implementando el algoritmo exacto de búsqueda exhaustiva)

La primera forma para resolver este problema será mediante la implementación del algoritmo de
búsqueda exhaustiva. La búsqueda búsqueda exhaustiva, también es conocida búsqueda combinato-
ria, búsqueda exhaustiva o sencillamente fuerza bruta, es una técnica trivial, que consiste en enumerar
sistemáticamente todos los posibles candidatos para la solución de un problema, con el objetivo de
determinar si dicho candidato satisface la solución al mismo.

La búsqueda por fuerza bruta es sencilla de implementar y, siempre que exista, encuentra una
solución. Sin embargo, su costo de ejecución es proporcional al número de soluciones candidatas,
el cual es exponencialmente proporcional al tamaño del problema. Por el contrario, la búsqueda por

52
fuerza bruta se usa habitualmente cuando el número de soluciones candidatas no es elevado.

Para resolver el problema primeramente se planteará el modelo matemático asociado a dicho prob-
lema:
Maximizar 3x1 + 4x2 + 5x3 + 6x4
Sujeto a 2x1 + 3x2 + 4x3 + 5x4 ≤ 5

Seguidamente, para lograr visualizar de una mejor manera la totalidad de posibles opciones de solu-
ción, se elabora un diagrama de árbol, el cual facilita la enumeración total de las soluciones posibles:

Figura 3.2: Diagrama de árbol

Al recorrer las ramas del árbol se va obteniendo el total de posibles soluciones al problema, las
cuales las expresaremos en forma de un vector como el siguiente [0 0 0 0] . El valor 0 en una posición
significa que ese objeto no se ingresará a la mochila, en cambio el valor 1 indica que el dicho objetos
si será parte de la mochila. Por tanto, el vector antes expuesto indica que de los cuatro objetos
posibles, a la mochila únicamente se meterá el artículo número 4.

Una vez encontradas y enumeradas todas las posibles soluciones, se procede a determinar con cuál de
ellas se obtiene el beneficio máximo, respetando la restricción de volumen. A continuación se muestra
una tabla donde se exponen las soluciones, el peso y beneficio a asociada a cada una de ellas.

53
 N° Posible solución Peso Valor
1 [0 0 0 0] 0 0
2 [0 0 0 1] 5 6
3 [0 0 1 0] 4 5
4 [0 0 1 1] 9 11
5 [0 1 0 0] 3 4
6 [0 1 0 1] 8 10
7 [0 1 1 0] 7 9
8 [0 1 1 1] 12 15
9 [1 0 0 0] 2 3
10 [1 0 0 1] 7 9
11 [1 0 1 0] 6 8
12 [1 0 1 1] 11 14
13 [1 1 0 0] 5 7
14 [1 1 0 1] 10 13
15 [1 1 1 0] 9 12
16 [1 1 1 1] 4 18

Tabla 3.2: Datos solución 1

De todas las posibles opciones de respuestas, sólo algunas de ellas satisfacen (1, 2, 3, 5, 9 y 13) la re-
stricción referida al peso de la mochila y de estas, la opción en la que se obtiene el valor máximo es la
número trece , en la cual se incluyen en la mochila los artículos 1 y 2, obteniendo el valor óptimo de 7.

Solución 2: (Implementando un algoritmo exacto de Programación Dinámica)

El objetivo básico en la Programación Dinámica consiste en "descomponer" un problema de

optimización en k variables a una serie de problemas con menor número de variables más fáciles de
resolver. Precisamente esto es lo que se hace en el Problema de la Mochila; reducir un problema ini-
cial de n variables a n problemas de 1 variable. En este sentido, se podría decir que la Programación
Dinámica se basa en un método de descomposición.

La técnica de Programación Dinámica evita explorar todas las secuencias posibles por medio de la
resolución de subproblemas de tamaño creciente y almacenamiento en una tabla de las soluciones
óptimas de esos subproblemas para facilitar la solución de los problemas más grandes. A contin-

54
uación se expone el algoritmo para resolver el problema propuesto.

Algoritmo Bottom up Approach

Para encontrar el valor máximo de la mochila:

para i=1 hasta n

dp [i][0] =0

para j=1 hasta w

dp [0] [j] =0
para i=1 hasta n
para j=1 hasta w
si peso [i] <= W
dp [i] [j] = max (dp [i-1] [j], dp [i-1] [j-peso[i]] + valor [i])
de lo contrario
dp [i] [j] = dp [i-1] [j]
Retornar dp [n] [w]

Para determinar los objetos que serán parte de la mochila:

Mientras i, j >0
si dp [i] [j] es distinto de dp [i-1] [j] ( el i elemento es parte de
la mochila)
y hacer i=i-1, j=j- peso[i]
de lo contrario
i=i-1 (asume que el elemento i-ésimo no está en la mochila)

Mediante la implementación del algoritmo lo que se hace es rellenar la siguiente matriz

N° Peso Valor
(Volumen) (Beneficio)
0 Posición 0
1 2 3
2 3 4
3 4 5
4 5 6

Tabla 3.3: Datos solución 2

55
El algoritmo, primeramente lo que hace es rellenar de cero la primera fila (fila 0) y primera columna
(columna 0), lo cual significa iniciar con una mochila nula, que tienen un valor asociado de cero. La
primera fila y columna se rellena de la siguiente manera:

para j=1 hasta 5

dp [0] [j]=0
para i=1 hasta 4
dp [i] [0]=0

Posteriormente se rellena cada una de las filas, comparando el peso (volumen) de los objetos
disponibles con el peso o capacidad de la mochila, si el peso de un objeto disponible es menor o igual
que el peso que soporta la mochila, entonces este objeto se introduce en la mochila, y se registra en
la matriz el valor asociado a dicho objeto. Por ejemplo, para la fila 1, el peso del primer objeto (2)
es mayor que el peso de la mochila (1), esto implica que no es posible introducir este objeto a esa
mochila y se procede a registrar cero en la correspondiente posición de la matriz. Luego se compara
el peso del mismo objeto con el peso de la siguiente capacidad de la mochila (2), como son iguales
entonces se introduce a la mochila el objeto 1 cuyo valor es 3. Mediante la implementación del
algoritmo se obtiene lo siguiente:

Para la fila 1:

i=1, j=1, entonces peso [1] >1

dp[1][1] = dp [0][1]=0

i=1, j=2, entonces peso [1] <= 2

dp[1][2] = max (dp [0][2], dp [0][2-2] + valor[1])
= max (0, 0 + 3) =3

i=1, j=3,entonces peso[1] <= 3

dp[1][3] = max (dp [0][3], dp [0][3-2] + valor[1])
= max (0, 0 + 3) =3

i=1, j=4, entonces peso[1] <=4

dp[1][4] = max (dp [0][4], dp [0][4-2] + valor[1])
= max (0, 0 + 3) =3

i=1, j=5, entonces peso[1] <=5

56
 dp[1][5] = max (dp [0][5], dp [0][50-2] + valor[1])
= max (0, 0 + 3) =3

De forma análoga, para la fila 2 tenemos:

i=2, j=1, entonces peso [2]>1

dp[2][1] = dp [1][1]=0

i=2, j=2, entonces peso [2]>2

dp[2][2] = dp [1][2]=3

i=2, j=3, entonces peso [2]<=3

dp[2][3] = max (dp [1][3], dp [1][3-3] + valor[2])
= max (3, 0 + 4) =4

i=2, j=4, peso [2]<=4

dp[2][4] = max (dp [1][4], dp [1][4-3] + valor[2])
= max (3, 0 + 4) =4

i=2, j=5, entonces peso [2]<=5

dp[2][5] = max (dp [1][5], dp [1][5-3] + valor[2])
= max (3, 3 + 4) =7

La siguiente fila se obtiene de la siguiente forma:

i=3, j=1, entonces peso [3]>1

dp[3][1] = dp [2][1]=0

i=3, j=2, entonces peso [3]>2

dp[3][2] = dp [2][2]=3

i=3, j=3, entonces peso [3]>3

dp[3][3] = dp [2][3]=4

i=3, j=4, entonces peso [3] <=4

dp[3][4] = max (dp [2][4], dp [2][4-4] + valor[3])
= max (4, 0 + 5) =5

57
i=3, j=5, entonces peso [3]<=5
dp[3][5] = max (dp [2][5], dp [2][5-4] + valor[3])
= max (7, 0 + 5) =7

Para calcular los valores de la última fila se procede de una manera similar:

i=4, j=1, entonces peso[4]>1

dp[4][1] = dp [3][1]=0

i=4, j=2, entonces peso [4]>2

dp[4][2] = dp [3][2]=3

i=4, j=3 , entonces peso [4]>3

dp[4][3] = dp [3][3]=4

i=4, j=4 , entonces peso [4]>4

dp[4][4] = dp [3][4]=5

i=4, j=5 , entonces peso [4]<=5

dp[4][5] = max (dp [3][5], dp [2][5-5] + valor[4])
= max (7, 0 + 5) =7

Como consecuencia de lo antes expuesto se obtiene la matriz que permite determinar el beneficio
máximo que se alcanza con esta mochila, que en este caso corresponde al valor 7, y que es justamente
el mismo valor generado mediante el algoritmo de fuerza bruta.

N° Peso Valor 0 1 2 3 4 5
(Volumen) (Beneficio)
0 Posición 0 0 0 0 0 0 0
1 2 3 0 0 3 3 3 3
2 3 4 0 0 3 4 4 7
3 4 5 0 0 3 4 5 7
4 5 6 0 0 3 4 5 7

Tabla 3.4: Datos solución 2

Es importante señalar que la tabla por sí sola, únicamente nos permite determinar la solución óptima
al problema de la mochila, pero hasta este momento no se conocen los objetos que se introducirán en

58
ella. Es justamente, la segunda parte del algoritmo quien nos permitirá solventar esta situación.

Este segunda parte del algoritmo consiste en comparar el último valor de la matriz con el de la fila
anterior (dp[i][j] 6= dp[i − 1][j]), si son distintos, el objeto i será parte de la mochila y se calcula un
nuevo i(i = i − 1), y un nuevo j(j = j − peso[i]), si ocurre que son iguales, entonces se descarta el
objeto i y se continua comparando, mientras i, j > 0.

Este procedimiento se muestra a continuación:

Como dp[4][5] = dp[3][5], entonces el objeto i = 4 se descarta, y lo mismo ocurre con los objetos
i = 3, puesto que ocurre dp[3][5] = dp[2][5], ahora bien, como dp[2][5] 6= dp[1][5], el objeto i = 2
será parte de la mochila y se procede a calcular un nuevo j, que en este caso sería j = 5 − 3 = 2,
luego se continua con la comparación: dp[1][2] 6= dp[0][2], esto hace indicar que el objeto i = 1 se
deberá incluir en la mochila y hacemos j = 2 − 2 = 0. El algoritmo se detiene aquí puesto que
debe ser j > 0, ante esta situación es posible afirmar que se está ante la presencia del valor óptimo
[1 1 0 0], es decir que los objetos que se deben meter a la mochila son el 1 y 2, obteniendo de esta
manera un valor máximo de 7.

Solución 3: (Implementando el algoritmo heurístico del coeficiente de rendimiento)

Un método heurístico es un procedimiento para resolver un problema de optimización bien definido

mediante una aproximación intuitiva, en la que la estructura del problema se utiliza de forma
inteligente para obtener una buena solución. Los algoritmos heurísticos son procedimientos simples
basados en el sentido común que se supone ofrecerán una buena solución, aunque no necesariamente
la óptima, a problemas difíciles, de un modo fácil y rápido.

Una importante ventaja que presentan las heurísticas respecto a las técnicas que buscan soluciones
exactas es que, por lo general, permiten una mayor flexibilidad para el manejo de las características
del problema. No suele resultar complejo diseñar algoritmos heurísticos. Además, generalmente ofre-
cen más de una solución, lo cual permite ampliar las posibilidades de elección del que decide, sobre
todo cuando existen factores no cuantificables que no han podido ser añadidos en el modelo, pero que
también deben ser considerados. Por otra parte, suele ser más fácil de entender la fundamentación
de las heurísticas que los complejos métodos matemáticos que utilizan la mayoría de técnicas exactas.

59
Una solución intuitiva pero que puede no ser óptima la podemos encontrar con un algoritmo que se
implementa de la siguiente forma:

• Ordenar la lista de objetos de forma descendente de acuerdo a la siguiente proporción

bi
ri =
vi

• Seleccionar los objetos hasta llenar la mochila.

• Ahora tenemos dos opciones: si el siguiente objeto ya no cabe completo en la mochila podemos
quedarnos con una fracción de él, obteniendo un beneficio igual a
pesototal − pesoactual
pesoobjeto

o no meter ningún objeto más en la mochila. La primera opción se elige cuando el problema es
de mochila fraccional y la segunda, cuando el problema es de mochila 0/1.

Al ejecutar el primer paso del algoritmo se obtiene la siguiente tabla:

Objeto b v r
1 3 2 1.5
2 4 3 1.3
3 5 4 1.2
4 6 5 1.2

Tabla 3.5: Datos solución 3

Mediante el segundo paso de la heurística mencionada, elegiríamos los productos 1 y 2, ya que al

tratar de ingresar el objeto 3 se estaría excediendo la capacidad permitida. Entonces la solución sería
[1 1 0 0], generando un beneficio de 7. Se puede notar que, en este caso la solución encontrada por el
heurístico coincide con la solución óptima, encontrada primeramente cuando enumeramos todas las
posibles opciones y luego al aplicar Programación Dinámica.

60
Solución 4: (Implementando la herramienta computacional WinQsb)

El WinQsb o simplemente QSB (Quantitative System Business), es un paquete de herramientas muy

versátil que contiene 19 módulos, que permiten el análisis y resolución de modelos matemáticos,
problemas administrativos, de producción, proyectos, inventarios, transporte, entre muchos otros.
Ofrece una interfaz básica pero amigable, es un software de ayuda a la toma de decisiones que
contiene herramientas muy útiles para resolver distintos tipos de problemas en el campo de la
Investigación de Operaciones.

Uno de estos 19 módulos está referido a la implementación de Programación Dinámica, y dentro de

esta se abordan los tres diferentes modelos:

• Problema de la Diligencia (Stagecoach Problem)

• Problema de la Mochila (Snapsack Problem)

• Programación de Producción e Inventarios (Production and Inventory Scheduling)

En el caso del problema que nos ocupa, el Problema de la Mochila, se desarrolla bajo dos con-
sideraciones, primero teniendo en cuenta el peso y luego el volumen. Este es un problema que
también podría resolverse por programación lineal entera teniendo en cuenta la función objetivo y
restricciones siguientes:

Siendo xj el elemento a transportar. Para el caso del volumen se reformaría la primera restricción
cambiando los coeficientes por los volúmenes de los ítems.

Sea j: la variable que representa el artículo:

• x(j) :el número de unidades cargadas del artículo j.

• w(j) :el espacio o el peso que demanda cada unidad del artículo j.

• R(jX(j) :la función del retorno del artículo j si se llevan x(j) unidades en la mochila, del artículo
j.

• g(j,w) :retorno de total acumulativo dado el espacio w disponible para el artículo j

• g(w) = máximo{R(jX(j)) + g[i − 1, w − W(j)X(j) ]}

61
Veamos entonces el procedimiento a seguir para resolver el problema con esta herramienta computa-
cional:

1. Elegir módulo de Programación Dinámica.

Figura 3.3: Módulo del WinQsb

2. Seleccionar nuevo problema y Knapsack Problem

Figura 3.4: Selección del problema

3. Ingresar los datos del problema

62
 Figura 3.5: Datos del problema

4. Mostrar la solución del problema

Figura 3.6: Solución del problema

La solución nos indica que se deben incluir a la mochila los objetos 1 y 2 los cuales generan un
retorno total de 7.

Ejemplo 3.2 Un naviero tiene un buque carguero con capacidad de hasta 500 toneladas. El carguero
transporta contenedores de diferentes pesos para una determinada ruta. En la ruta actual el carguero
puede transportar algunos de los siguientes contenedores:

Contenedor 1 2 3 4 5
Peso en (cientos de toneladas) 1 2 1 3 4
Valor (miles de dólares) 3 5 4 6 7

Tabla 3.6: Datos ejemplo 3.2

63
El analista de la empresa del armador desea determinar el envío (conjunto de contenedores) que
maximiza el valor de la carga transportada.

Solución 1: (Implementando el algoritmo exacto de búsqueda exhaustiva)

El modelo matemático del problema es el siguiente:

Maximizar 3x1 + 5x2 + 4x3 + 6x4 + 7x5

Sujeto a x1 + 2x2 + x3 + 3x4 + 4x5 ≤ 5

N° Posible solución Peso Valor

1 [0 0 0 0 0] 0 0
2 [0 0 0 0 1] 4 7
3 [0 0 0 1 0] 3 6
4 [0 0 0 1 1] 7 13
5 [0 0 1 0 0] 1 4
6 [0 0 1 0 1 ] 5 11
7 [0 0 1 1 0] 4 10
8 [0 0 1 1 1] 8 17
9 [0 1 0 0 0] 2 5
10 [0 1 0 0 1] 6 12

Tabla 3.7: Datos solución 1

64
 N° Posible solución Peso Valor
11 [0 1 0 1 0] 5 11
12 [0 1 0 1 1] 9 18
13 [0 1 1 0 0] 3 9
14 [0 1 1 0 1] 7 16
15 [0 1 1 1 0] 6 15
16 [0 1 1 1 1] 10 22
17 [1 0 0 0 0] 1 3
18 [1 0 0 0 1] 5 10
19 [1 0 0 1 0] 4 9
20 [1 0 0 1 1] 8 16
21 [1 0 1 0 0] 2 7
22 [1 0 1 0 1] 6 14
23 [1 0 1 1 0] 5 13
24 [1 0 1 1 1] 9 20
25 [1 1 0 0 0] 3 8
26 [1 1 0 0 1] 7 15
27 [1 1 0 1 0] 6 14
28 [1 1 0 1 1] 10 21
29 [1 1 1 0 0] 4 12
30 [1 1 1 0 1] 8 19
31 [1 1 1 1 0] 7 18
32 [1 1 1 1 1] 11 25

Tabla 3.8: Datos solución 1

De la matriz anterior es posible apreciar que de todas las posibles opciones, la opción número 23,
[1 0 1 1 0] es la que satisface la restricción referida al peso y que maximiza el valor de la carga
transportada. En este caso los contenedores que deben enviar son el 1, 3 y 4 con lo cual se obtendrá
una ganancia de $ 13000.

Solución 2: (Implementando un algoritmo exacto de Programación Dinámica).

Es importante recordar que con la ejecución de la primer parte del algoritmo el objetivo principal es
la construcción de la siguiente matriz

65
 N° Peso Valor 0 1 2 3 4 5
(Volumen) (Beneficio)
0 Posición 0
1 1 3
2 2 5
3 1 4
4 3 6
5 4 7

Tabla 3.9: Datos solución 2

La fila 0 y la columna 0 se rellena de ceros de la siguiente manera:

para j=1 hasta 5

dp[0][j]=0

para i=1 hasta 5

dp[i][0]=0

Posteriormente procedemos a rellenar la fila 1:

i=1, j=1, entonces peso[1]<=1

dp[1][1] = max (dp [0][1], dp [0][1-1] + valor[1])
= max (0, 0 + 3)=3

i=1, j=2, entonces peso [1]<=2

dp[1][2] = max (dp [0][2], dp [0][2-1] + valor[1])
= max (0, 0 + 3)=3

i=1, j=3, entonces peso[1]<=3

dp[1][3] = max (dp [0][3], dp [0][3-1] + valor[1])
= max (0, 0 + 3)=3

i=1, j=4, entonces peso[1]<=4

dp[1][4] = max (dp [0][4], dp [0][4-1] + valor[1])
= max (0, 0 + 3)=3

66
i=1, j=5, entonces peso[1]<=5
dp[1][5] = max (dp [0][5], dp [0][5-1] + valor[1])
= max (0, 0 + 3)=3

Para la fila 2 tenemos:

i=2, j=1, entonces peso [2]>1

dp[2][1] = dp [1][1]=3

i=2, j=2, entonces peso [2]<=2

dp[2][2] = max (dp [1][2], dp [1][2-2] + valor[2])
= max (3, 0 + 5) =5

i=2, j=3, entonces peso [2]<=3

dp[2][3] = max (dp [1][3], dp [1][3-2] + valor[2])
= max (3, 3 + 5)=8

i=2, j=4, entonces peso [2]<=4

dp[2][4] = max (dp [1][4], dp [1][4-2] + valor[2])
= max (3, 3+5)=8

i=2, j=5, entonces peso [2]<=5

dp[2][5] = max (dp [1][5], dp [1][5-2] + valor[2])
= max (3, 3 + 5)=8

Para la fila 3 se tiene:

i=3, j=1, entonces peso[3]<=1

dp[3][1] = max (dp [2][1], dp [2][1-1] + valor[3])
= max (3, 0 + 4)=4

i=3, j=2, entonces peso [3]<=2

dp[3][2] = max (dp [2][2], dp [2][2-1] + valor[3])
= max (5, 3 + 4)=7

i=3, j=3, entonces peso [3]<=3

dp[3][3] = max (dp [2][3], dp [2][3-1] + valor[3])
= max (8, 5 + 4)=9

67
i=3, j=4, entonces peso [3]<=4
dp[3][4] = max (dp [2][4], dp [2][4-1] + valor[3])
= max (8, 8 + 4)=12

i=3, j=5, entonces peso [3]<=5

dp[3][5] = max (dp [2][5], dp [2][5-1] + valor[3])
= max (8, 8 + 4)=12

Para la fila 4:

i=4, j=1, entonces peso[4]>1

dp[4][1] = dp [3][1]=4

i=4, j=2, entonces peso [4]>2

dp[4][2] = dp [3][2]=7

i=4, j=3, entonces peso [4]<=3

dp[4][3] = max (dp [3][3], dp [3][3-3] + valor[4])
= max (9, 0 + 6)=9

i=4, j=4, entonces peso [4]<=4

dp[4][4] = max (dp [3][4], dp [3][4-3] + valor[4])
= max (12, 4 + 6)=12

i=4, j=5, entonces peso [4]<=5

dp[4][5] = max (dp [3][5], dp [2][5-3] + valor[4])
= max (12, 7 + 6)=13

Para la fila 5:

i=5, j=1, entonces peso[5]>1

dp[5][1] = dp[4][1]=4

i=5, j=2, entonces peso [5]>2

dp[5][2] = dp[5][2]=7

i=5, j=3, entonces peso [5]>3

68
 dp[5][3] = dp[4][3]=9

i=5, j=4, entonces peso [5]<=4

dp[5][4] = max (dp [4][4], dp [4][4-4] + valor[5])
= max (12, 0 + 7)=12

i=5 j=5, entonces peso [5]<=5

dp[5][5] = max (dp [4][5], dp [4][5-4] + valor[5])
= max (13, 4 + 7)=13

Finalmente, obtenemos la siguiente matriz:

N° Peso Valor 0 1 2 3 4 5
(Volumen) (Beneficio)
0 Posición 0 0 0 0 0 0 0
1 1 3 0 3 3 3 3 3
2 2 5 0 3 5 8 8 8
3 1 4 0 4 7 9 12 12
4 3 6 0 4 7 9 12 13
5 4 7 0 4 7 9 12 13

Tabla 3.10: Datos solución 2

Luego aplicamos la parte del algoritmo que nos permite determinar los objetos que serán parte de la
mochila:

Como dp[5][5] = dp[4][5], entonces el objeto i = 5 se descarta, luego como dp[4][5] 6= dp[3][5],
el objeto i = 4 será parte de la mochila y se procede a calcular un nuevo j, que en este caso sería
j = 5 − 3 = 2, luego se continua con la comparación: dp[3][2] 6= dp[2][2], esto hace indicar que el
objeto i = 3 se deberá incluir en la mochila y hacemos j = 2 − 1 = 1, como dp[2][1] = dp[1][1],
entonces el objeto i = 2 no se incluye, después se observa que dp[1][1] 6= dp[0][1], entonces el objeto
i = 1 también se mete a la mochila. Al llegar a j = 0 el algoritmo se detiene aquí puesto que debe ser
j > 0, ante esta situación es posible afirmar que se está ante la presencia del valor óptimo [1 0 1 1 0],
es decir que los objetos que se deben meter a la mochila son el 1, 3 y 4 obteniendo de esta manera un
valor máximo de 1300.

69
Solución 3: (Implementando el algoritmo heurístico coeficiente de rendimiento)

Recordemos que el algoritmo heurístico propuesto funciona de la siguiente manera:

1. Ordenar los objetos de forma descendente de acuerdo al cociente bi /vi .

2. Seleccionar los objetos hasta llenar la mochila.

3. Ahora, si el siguiente objeto ya no cabe completo en la mochila, entonces no meter ningún

objeto más.

Procediendo a implementar los pasos del algoritmo obtenemos:

Objeto b v r
1 4 1 4
2 3 1 3
3 5 2 2.5
4 6 3 2
5 7 4 1.7

Tabla 3.11: Datos solución 3

El segundo paso del algoritmo nos permite tomar la decisión de meter a la mochila los primeros tres
productos, ya que el hecho de ingresar el objeto 4 excedería la capacidad permitida. Por tanto la
solución sería [1 1 1 0 0], generando un beneficio de 13000 dólares. Se puede notar que, en este caso
la solución encontrada por el heurístico coincide con la solución óptima, encontrada primeramente
cuando enumeramos todas las posibles opciones y luego al aplicar Programación Dinámica.

70
Solución 4: (Implementando la herramienta computacional WinQsb)

1. Seleccionar un nuevo problema Knapsack Problem.

Figura 3.7: Selección del problema

2. Ingresar los datos del problema

Figura 3.8: Datos del problema

71
 3. Mostrar la solución del problema

Figura 3.9: Solución del problema

La solución nos indica que se deben incluir a la mochila los objetos 1, 3 y 4 los cuales generan un
retorno total de 13.

Ejemplo 3.3 Se debe realizar un envío de 10 objetos distintos. El beneficio y volumen aparecen en
la siguiente tabla:

N° Beneficio Volumen
(Dólares) (cm3 )
1 70 10
2 90 20
3 90 30
4 80 40
5 100 50
6 80 60
7 90 70
8 150 80
9 130 90
10 140 100

Tabla 3.12: Datos del ejemplo 3.3

Determinar el envío máximo que no exceda un volumen de 100 cm3 .

72
Solución 1: (Implementando un algoritmo exacto de Programación Dinámica)

En este caso, se tiene un total de 10 objetos (n = 10) y una restricción de volumen de 80m3 (W = 80),
para ello modelo matemático asociado al problema es el que sigue:

Maximizar 70x1 + 90x2 + 30x3 + 80x4 + 100x5 + 80x6 + 90x7 + 150x8 + 130x9 + 140x10
Sujeto a 10x1 + 20x2 + 30x3 + 40x4 + 50x5 + 60x6 + 70x7 + 80x8 + 90x9 + 100x10 ≤ 100

Resolver este problema mediante el algoritmo de la búsqueda exhaustiva implicaría un espacio de

posibles soluciones de 210 = 1024, es por ello que resulta poco razonable aplicarlo.

Entonces se hace necesario la implementación de otra forma de resolver el problema, a continuación

se muestra una:

Con el algoritmo se llena la siguiente matriz

Volumen Beneficio 0 10 20 30 40 50 60 70 80
Posición 0
10 70
20 90
30 90
40 80
50 100
60 80
70 90
80 150
90 130
100 140

Tabla 3.13: Datos solución 1

Para rellenar la primera columna y primera fila:

para j=1 hasta 8

dp [0] [j] =0

para i=1 hasta 10

73
 dp [i] [0] =0

Para rellenar la primer columna:

i=1, j=1, entonces peso[1]<=10

dp[1][1] = max (dp [0][1], dp [0][10-10] + valor[1])
= max (0, 0 + 70)

i=1, j=2, entonces peso [1]<=20

dp[1][2] = max (dp [0][2], dp [0][20-10] + valor[1])
= max (0, 0 + 70) =70

i=1, j=3, entonces peso[1]<=30

dp[1][3] = max (dp [0][3], dp [0][30-10] + valor[1])
= max (0, 0 + 70) =70

i=1, j=4, entonces peso[1]<=40

dp[1][4] = max (dp [0][4], dp [0][40-10] + valor[1])
= max (0, 0 + 70) =70
i=1, j=5, entonces peso[1] <=50
dp[1][5] = max (dp [0][5], dp [0][50-10] + valor[1])
= max (0, 0 + 70) =70

i=1, j=6, entonces peso[1]<=60

dp[1][6] = max (dp [0][6], dp [0][60-10] + valor[1])
= max (0, 0 + 70) =70

i=1, j=7, entonces peso[1]<=70

dp[1][7] = max (dp [0][7], dp [0][70-10] + valor[1])
= max (0, 0 + 70) =70

i=1, j=8, entonces peso[1]<=80

dp[1][8] = max (dp [0][8], dp [0][80-10] + valor[1])
= max (0, 0 + 70) =70

74
Para la fila 2 tenemos:

i=2, j=1, entonces peso[2]>10

dp[2][1] = dp [1][1]=70

i=2, j=2, entonces peso [2] <= 20

dp[2][2] = max (dp [1][2], dp [1][20-20] + valor[2])
= max (70, 0 + 90)=90

i=2, j=3, entonces peso [2] <= 30

dp[2][3] = max (dp [1][3], dp [1][30-20] + valor[2])
= max (70, 70 + 90)=160

i=2, j=4, entonces peso [2]<= 40

dp[2][4] = max (dp [1][4], dp [1][40-20] + valor[2])
= max (70, 70 + 90)=160

i=2, j=5, entonces peso [2]<= 50

dp[2][5] = max (dp [1][5], dp [1][50-20] + valor[2])
= max (70, 70 + 90)=160

i=2, j=6, entonces peso [2]<= 60

dp[2][6] = max (dp [1][6], dp [1][60-20] + valor[2])
= max (70, 70 + 90)=160

i=2, j=7 , entonces peso [2]<= 70

dp[2][7] = max (dp [1][7], dp [1][70-20] + valor[2])
= max (70, 70 + 90)=160

i=2, j=8, entonces peso [2] <= 80

dp[2][8] = max (dp [1][7], dp [1][80-20] + valor[2])
= max (70, 70 + 90)=160

75
Las filas que siguen de obtienen de manera similar y a partir de esto obtenemos la siguiente matriz:

Volumen Beneficio 0 10 20 30 40 50 60 70 80
Posición 0 0 0 0 0 0 0 0 0 0
10 70 0 70 70 70 70 70 70 70 70
20 90 0 70 90 160 160 160 160 160 160
30 90 0 70 90 160 160 180 250 250 250
40 80 0 70 90 160 160 180 250 250 250
50 100 0 70 90 160 160 180 250 250 260
60 80 0 70 90 160 160 180 250 250 260
70 90 0 70 90 160 160 180 250 250 260
80 150 0 70 90 160 160 180 250 250 260
90 130 0 70 90 160 160 180 250 250 260
100 140 0 70 90 160 160 180 250 250 260

Tabla 3.14: Datos solución 1

El valor que maximiza la función objetivo se aprecia en la última fila, última columna de la tabla
anterior (260) y para determinar cuáles son los objetos que se ingresarán a la mochila se implementa
la segunda parte del algoritmo, el cual consiste en comparar el último valor de la matriz con el de la
fila anterior (dp[i][j] 6= dp[i−1][j]), si son distintos, el objeto i será parte de la mochila y se calcula un
nuevo i (i = i − 1), y un nuevo j (j = j − peso[i]), si ocurre que son iguales, entonces se descarta el
objeto i y se continua comparando, mientras i, j > 0. Este procedimiento se muestra a continuación:

Como dp[10][8] = dp[9][8], entonces el objeto i = 10 se descarta, y lo mismo ocurre con los
objetos i = 9, i = 8, i = 7, i = 6, puesto que para cada uno de ellos ocurre dp[10][8] = dp[9][8],
dp[9][8] = dp[8][8], dp[8][8] = dp[7][8], dp[7][8] = dp[6][8], dp[6][8] = dp[5][8], ahora bien, como
dp[5][8] 6= dp[4][8], el objeto j = 5 será parte de la mochila y se procede a calcular un nuevo j,
que en este caso sería j = 8 − 5 = 3, luego se continua con la comparación: dp[4][3] = dp[3][3],
dp[3][3] = dp[2][3] lo que implica que el objeto 4 y 3 no serán parte de la mochila. Procediendo de
forma análoga, se tiene que dp[2][3] 6= dp[1][3], luego el objeto 2 se deberá incluir en la mochila y
hacemos j = 3 − 2 = 1, después se tiene que dp[1][1] 6= dp[0][1], y por tanto el objeto j = 1 también
será parte de la mochila, además como i = 0 el algoritmo se detiene y se está ante la presencia del
valor óptimo [1 1 0 0 1 0 0 0 0 0], es decir que los objetos que se deben meter a la mochila son el 1, 2
y 5, obteniendo de esta manera un valor máximo de 260.

76
Solución 2: (Implementando el algoritmo heurístico del coeficiente de rendimiento):
Al ejecutar el primer paso del algoritmo se obtiene la siguiente tabla:

Objeto b v r
1 70 10 7
2 90 20 4.5
3 90 30 3
4 80 40 2
5 100 50 2
8 150 80 1.8
9 130 90 1.4
10 140 100 1.4
6 80 60 1.3
7 90 70 1.2

Tabla 3.15: Datos solución 2

Mediante el segundo paso de la heurística mencionada, elegiríamos los productos 1, 2 y 3, ya que

al tratar de ingresar el objeto 4 se estaría excediendo la capacidad permitida. Entonces la solución
sería [1 1 1 0 0 0 0 0 0 0], generando un beneficio de 250. Se puede notar que aunque la solución no
es la óptima, si es una muy buena aproximación, la cual se obtiene en menos tiempo que el método
expuesto en las solución 1.

Solución 3: (Aplicando la herramienta computacional WinQsb)

1. Seleccionar un nuevo problema Knapsack Problem

Figura 3.10: Selección del problema

77
 2. Ingresar los datos del problema

Figura 3.11: Datos del problema

3. Mostrar la solución del problema

Figura 3.12: Solución del problema

La solución nos indica que se deben incluir a la mochila los objetos 1, 2 y 9 con los cuales se obtiene
un valor máximo de 260.

78
3.4 Problemas propuestos

1. Un barco de 4 toneladas puede cargarse con uno o más de tres artículos. La siguiente tabla da el
peso unitario,pi , en toneladas y el ingreso unitario en miles de dólares, ri , para el artículo i . El
objetivo es determinar la cantidad de unidades de cada artículo que maximizará el rendimiento
total.

Artículo Peso Beneficio

i (Toneladas) ($)
1 2 31
2 3 47
3 1 14

Tabla 3.16: Datos del problema 1

2. Resolver el problema de la mochila para la siguiente instancia:

Objeto Peso Valor

(grs) ($)
1 150 20
2 325 40
3 600 50
4 805 36
5 430 25
6 1200 64
7 770 54
8 60 18
9 930 46
10 353 28

Tabla 3.17: Datos del problema 2

El peso máximo soportado por la mochila es de 2400grs.

79
3. Se debe realizar un envío de 7 objetos distintos. El valor, peso y volumen aparecen en la sigu-
iente tabla:

Objeto Valor Volumen

(Euros) cm3
1 56 21
2 71 16
3 69 17
4 91 28
5 70 12
6 85 31
7 65 9

Tabla 3.18: Datos del problema 3

Determinar el envío máximo que no exceda el volumen de 90cm3 .

4. Una empresa de transporte marítimo de mercancías posee un barco con una bodega cuya ca-
pacidad es de 205cm3 . Se desea transportar cuatro bienes de los que se dispone su volumen y
su valor monetario. En la siguiente tabla se muestra dicha información:

Bienes Volumen Ingreso

(cm3 /Tm) ($)
1 70 1250
2 50 900
3 60 1000
4 75 1200

Tabla 3.19: Datos del problema 4

Se trata de determinar la cantidad de T m. de cada bien que se debe transportar en cada bodega
de forma que el ingreso sea máximo.

80
5. Un camión puede transportar un total de 10 toneladas de productos. Hay cinco clases de pro-
ductos para transportar, cuyo peso y valor se muestran en la siguiente tabla. Suponiendo que por
lo menos se debe transportar un artículo de cada clase, determinar el cargamento que maximiza
el valor total.

Clase Peso Valor

(Tm) (miles de
dólares)
A 2 1 000
B 5 2 000
C 6 1800
D 3 900
E 4 2100

Tabla 3.20: Datos del problema 5

81