BENEMÉRITA UNIVERSIDAD AUTÓNOMA DE PUEBLA

MAESTRÍA EN CIENCIAS DE LA COMPUTACIÓN

ANÁLISIS Y DISEÑO DE ALGORITMOS

DRA. MIREYA VIDAL TOVAR

OTOÑO 2023

TÉCNICAS DE DISEÑO: PROGRAMACIÓN DINÁMICA

SÁNCHEZ GONZÁLEZ, MARIO Mat.: 223470505

HERNÁNDEZ FLORES, MARIA DEL ROCIO Mat.: 223470495

Objetivos

Objetivo general:

Desarrollar, analizar y comparar la complejidad temporal de dos algoritmos que modelen la

solución al problema de la Mochila Binaria.

Objetivos específicos:

I. Codificar dos algoritmos que modelen la solución al problema de la Mochila Binaria, uno
tradicional y otro en el que se implemente la técnica de programación dinámica.

II. Utilizar instancias de diversos tamaños (n = 10,100,1000 y 4000) para obtener

respectivos los tiempos de ejecución.

III. Realizar un gráfico con los valores obtenidos para ambos algoritmos y comparar su
comportamiento.

IV. Obtener las constantes experimentales y predecir el tiempo de ejecución para instancias
de tamaños mayores a los utilizados.
 1. INTRODUCCIÓN

La notación asintótica es una pieza fundamental en el análisis de algoritmos ya que

permite identificar la complejidad temporal del algoritmo, es decir, cuanto tiempo tarda en
ejecutarse según el número de datos de entrada asignados, por lo que su uso ayuda a conocer
las diferencias que permitirán decidir cuál es la opción optima a implementar.

Las técnicas de diseño de algoritmos son una parte crucial para el desarrollo de programas
que resuelvan problemas de manera eficaz y generar una estructura que desglose una solución
de forma sistemática. Existen diversas técnicas como divide y vencerás, programación dinámica,
back tracking, algoritmos heurísticos, entre otros.

En el caso de la programación dinámica, esta se centra en descomponer un problema en

subproblemas, resolverlos independientemente mientras guarda las soluciones obtenidas para
posteriormente acoplar los resultados obtenidos y conseguir una solución.

1.1. El problema de la mochila.

Los problemas de optimización combinatoria son aquellos que tienen un conjunto de

soluciones discreto, es decir, una cantidad finita de soluciones posibles. Esta rama de la
optimización está relacionada con la investigación operativa, teoría algorítmica y de la
complejidad computacional. Los algoritmos de optimización combinatoria se enfocan en
resolver problemas con un espacio amplio de soluciones al problema en cuestión y buscan
reducir el tamaño del espacio de búsqueda y exploración eficiente.

El problema de la mochila o “knapsack problem” es un problema de optimización

combinatoria el cuál plantea lo siguiente:

“Se tiene una determinada instancia de KP con un conjunto de objetos 𝑁, que consiste de 𝑛
objetos 𝑖 con ganancia 𝑝𝑖 y peso 𝑤𝑖 , y una capacidad 𝑐. (Usualmente, enteros positivos). El
objetivo es seleccionar un subconjunto de 𝑁 tal que la ganancia total de esos objetos
seleccionados es maximizada y el total de los pesos no excede a 𝑐” (Velasco, J).

El problema base está orientado hacia un conjunto finito de artículos con un peso
 específico y que deben ser guardados en un contenedor o mochila con capacidad limitada y
puede ser representado por las Ec. 1-3:

𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 ∑𝑛𝑖=1 𝑝𝑖 𝑥𝑖 (1)

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ∑𝑛𝑖=1 𝑤𝑖 𝑥𝑖 ≤ 𝑐 , (2)

𝑥𝑖 ∈ {0,1}, 𝑖 = 1, … , 𝑛 (3)

Donde:

𝑝𝑖 - Ganancia

𝑥𝑖 - Variables de decisión

𝑤𝑖 - Peso del ítem 𝑖

𝑐 – Capacidad total de la mochila

𝑛 – Número de ítems

Existen diferentes variaciones al problema dependiendo a las restricciones que se quieran

aplicar al problema base, una de ellas es “la Mochila Binaria” o “0-1 Knapsack Problem” en el que
cada objeto se escoge o no, no se puede fragmentar, por lo que se tienen dos opciones para cada
objeto 𝑖:

 El objeto 𝑖 no se agrega:

𝑉[𝑖. 𝑗] = 𝑉[𝑖 − 1, 𝑗] (4)

 El objeto 𝑖 se agrega: una vez seleccionado el objeto 𝑖, la ganancia 𝑝𝑖 aumenta y la

capacidad de la mochila se reduce 𝑐 − 𝑤𝑖 , por lo tanto:

𝑉[𝑖. 𝑗] = 𝑝𝑖 + 𝑉[𝑖 − 1, 𝑗 − 𝑤𝑖 ]. (5)

Como se requiere maximizar la ganancia respecto a los objetos seleccionados, se tiene que:

𝑉[𝑖, 𝑗] = máx(𝑉[𝑖 − 1, 𝑗], 𝑤𝑖 + 𝑉[𝑖 − 1, 𝑗 − 𝑤𝑖 ]) (6)

1.2. Algoritmo tradicional.

Para este caso, se propone un algoritmo que sigue los siguientes pasos:

1. Inicialización de la Matriz dp:

 Se crea una matriz dp de tamaño (𝑛 + 1) 𝑥 (𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑 + 1) para almacenar
resultados intermedios.
 Se inicializan las primeras fila y columna de la matriz dp con valores
predeterminados.
2. Llenado de la Matriz dp:
 Se itera sobre cada elemento 𝒊 y cada capacidad 𝒘.
 Si el peso del elemento actual (𝒑𝒆𝒔𝒐𝒔[𝒊 − 𝟏]) es menor o igual a la capacidad
actual (𝒘):
 Se considera la posibilidad de incluir o no el elemento en la mochila.
 Se actualiza 𝒅𝒑[𝒊][𝒘] con el máximo entre el valor actual y el valor sin
incluir el elemento.
 Si el peso del elemento es mayor que la capacidad actual, se copia el resultado
anterior.
3. Solución:
 El valor máximo que se puede obtener se encuentra en 𝒅𝒑[𝒏][𝒄𝒂𝒑𝒂𝒄𝒊𝒅𝒂𝒅].
Este proceso puede ser descrito con el siguiente pseudocódigo:
Función MochilaIterativa(capacidad, pesos[], valores[], n):
// Inicializar una matriz para almacenar resultados intermedios
Crear una matriz dp de tamaño (n+1) x (capacidad+1)
// Inicializar la primera fila y columna de la matriz
Para cada capacidad w desde 0 hasta capacidad:
dp[0][w] = 0
Para cada elemento i desde 0 hasta n:
dp[i][0] = 0

// Llenar la matriz mediante un enfoque iterativo

Para cada elemento i desde 1 hasta n:
Para cada capacidad w desde 1 hasta capacidad:
Si pesos[i-1] <= w:
// Considerar la posibilidad de incluir o no el elemento en la mochila
dp[i][w] = max(valores[i-1] + dp[i-1][w-pesos[i-1]],
dp[i-1][w])
Sino:
 / Si el peso del elemento es mayor que la capacidad actual, copiar
el resultado anterior
dp[i][w] = dp[i-1][w]

// El valor máximo que se puede obtener está en dp[n][capacidad]

Devolver dp[n][capacidad]

Como se puede observar, el algoritmo se centra en generar iteraciones a base de ciclos

para observar resultados posibles, pero son resultados que no son almacenados, son resultados
momentáneos, que involucran un numero grande de operaciones que puede resultar en un uso
mayor de recursos.

Para ilustrar su funcionamiento, se considera una mochila de capacidad igual a 5 y los

siguientes elementos:
 Elemento 1: Peso = 2, Valor = 3
 Elemento 2: Peso = 3, Valor = 4
 Elemento 3: Peso = 4, Valor = 5
 Elemento 4: Peso = 5, Valor = 8
Aplicando los pasos descritos anteriormente, se inicializa la matriz para almacenar los resultados
intermedios de tamaño (𝑛 + 1) 𝑥 (𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑 + 1). En este caso, 𝑛 = 4 es el número de
elementos y la capacidad es 5, lo cual se reflejan de la siguiente manera:

0 0 0 0 0 0

| | | | |

1 2 3 4 5

Luego se realizan iteraciones con cada elemento y peso, llenando la matriz:

 Elemento 1 (Peso = 2, Valor = 3):

0 0 0 0 0 0

0 | | | | |

1 | 0 0 3 3 3
  Elemento 2 (Peso = 3, Valor = 4):

0 0 0 0 0 0

0 | | | | |

1 | 0 0 3 3 3

2 | 0 0 3 4 4

 Elemento 3 (Peso = 4, Valor = 5):

0 0 0 0 0 0

0 | | | | |

1 | 0 0 3 3 3

2 | 0 0 3 4 4

3 | 0 0 3 5 5

 Elemento 4 (Peso = 5, Valor = 8):

0 0 0 0 0 0

0 | | | | |

1 | 0 0 3 3 3

2 | 0 0 3 4 4

3 | 0 0 3 5 5

4 | 0 0 3 5 8

Con todos los elementos iterados, se elige el valor más grande que es 8, lo cual se logra
seleccionando el elemento 2 y 4. Este ejemplo demuestra cómo el algoritmo de la mochila
iterativo construye una tabla para optimizar la selección de elementos que maximizan el valor
total sin exceder la capacidad de la mochila.
 La complejidad temporal del algoritmo está dada por la Ec. 7:

𝑂(𝑛 ∗ 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑) (7)

1.2. Algoritmo con la técnica de programación dinámica implementada

Este algoritmo funciona de manera similar al algoritmo iterativo propuesto

anteriormente, con la diferencia de que este método guarda los valores de las operaciones que
realiza

Los pasos que sigue este algoritmo son los siguientes:

1. Inicialización de la Tabla dp:

 Se crea una tabla dp de tamaño (𝑛 + 1) 𝑥 (𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑 + 1) para almacenar
resultados intermedios.
2. Llenado de la Tabla dp:
 Se itera sobre cada elemento 𝒊 y cada capacidad 𝒘.
 Si se considera el primer objeto 𝑖 = 0 o la capacidad de la mochila 𝑤 = 0, el valor
asociado en la matriz es 0
 Si el peso del elemento actual (𝒑𝒆𝒔𝒐𝒔[𝒊 − 𝟏]) es menor o igual a la capacidad
actual (𝒘):
 Se compara el valor de no incluir el objeto (𝒎𝒂𝒕𝒓𝒊𝒛[𝒊 − 𝟏][𝒘]) con el
valor de incluir el objeto (𝒗𝒂𝒍𝒐𝒓𝒆𝒔[𝒊 − 𝟏] + 𝒎𝒂𝒕𝒓𝒊𝒛[𝒊 − 𝟏][𝒘 −
𝒑𝒆𝒔𝒐𝒔[𝒊 − 𝟏]]) y se selecciona el valor máximo de estas dos opciones
colocándolo en 𝑚𝑎𝑡𝑟𝑖𝑧[𝑖][𝑤]
 Si el peso del elemento es mayor que la capacidad actual, se copia el resultado
anterior.
3. Solución:
 El valor máximo que se puede obtener se encuentra en 𝒅𝒑[𝒏][𝒄𝒂𝒑𝒂𝒄𝒊𝒅𝒂𝒅].
El pseudocódigo de la Mochila Binaria es el siguiente:

Función MochilaBinariaDinamica(capacidad, pesos[], valores[], n):

// Inicializar una tabla para almacenar resultados intermedios
Crear una tabla dp de tamaño (n+1) x (capacidad+1)
 // Llenar la tabla mediante programación dinámica
Para cada elemento i desde 0 hasta n:
Para cada capacidad w desde 0 hasta capacidad:
Si i == 0 o w == 0:
matriz[i][w] = 0
Sino, si pesos[i-1] <= w:
// Considerar la posibilidad de incluir o no el elemento
en la mochila
dp[i][w] = max(valores[i-1] + dp[i-1][w-pesos[i-1]],
dp[i-1][w])
Sino:
// Si el peso del elemento es mayor que la capacidad
actual, copiar el resultado anterior
dp[i][w] = dp[i-1][w]
// El valor máximo que se puede obtener está en
dp[n][capacidad]
Devolver dp[n][capacidad]
Considerando las mismas condiciones que en el ejemplo del método iterativo, capacidad igual
a 5 y los elementos:
 Elemento 1: Peso = 2, Valor = 3
 Elemento 2: Peso = 3, Valor = 4
 Elemento 3: Peso = 4, Valor = 5
 Elemento 4: Peso = 5, Valor = 8
Se inicializa la matriz (𝑛 + 1) 𝑥 (𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑 + 1) con n=4 (número de elementos) y la capacidad
es 5 de la siguiente manera:

Iterando y llenando la matriz:

 Elemento 0:

 Elemento 1 (Peso = 2, Valor = 3):

 Elemento 2 (Peso = 3, Valor = 4):

 Elemento 3 (Peso = 4, Valor = 5):

  Elemento 4 (Peso = 5, Valor = 8):

Este ejemplo ilustra cómo el algoritmo de la Mochila Binaria con programación dinámica llena
una tabla para optimizar la selección de elementos y obtener el valor máximo sin exceder la
capacidad de la mochila.

Este algoritmo tiene una complejidad temporal dada por la Ec. 8:

𝑂(𝑛 ∗ 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑) (8)

2. DESARROLLO

2.1. Justificación del lenguaje de programación.

Se optó por realizar la implementación de los algoritmos Java debido a que cuenta con las
siguientes ventajas:

I. Portabilidad: es un lenguaje que puede ejecutarse en múltiples entornos sin la necesidad

de hacer grandes modificaciones al sistema donde va a ser ejecutado.
II. Lenguaje Orientado a Objetos: representa es la posibilidad de programar de forma
modular y estructurada, lo que facilita el mantenimiento y escalabilidad de un software a
largo plazo.
III. Gran comunidad y soporte: es un lenguaje de programación muy empleado por los
programadores para el desarrollo de software, lo que hace posible encontrar
información, manuales y tutoriales para el desarrollo de proyectos.
IV. Seguridad: cuenta con políticas de seguridad para evitar que sea utilizado con fines
maliciosos.
 V. Rendimiento: es un lenguaje que ha sido mejorado con el paso de los años con métodos
de optimización y técnicas de compilación como Just-In-Time (JTI) que ayudan a crear
programas con la posibilidad de ser optimizados.

2.2. Diseño y análisis del algoritmo.

2.2.1. Algoritmo Mochila Iterativa.

En el Apéndice 1 se encuentra el código escrito en lenguaje Java para la solución al problema de
la Mochila Binaria de manera iterativa.

La capacidad de la mochila se fijó en un valor de 10 y las instancias usadas para el análisis

de complejidad temporal fueron de tamaño 𝑛 = 10, 50, 100, 250, 500, 750 y 1000. Para cada
tamaño de la instancia, se obtuvieron 5 tiempos con la finalidad de obtener un promedio de los
tiempos de ejecución cuyos valores se muestran en la tabla 1.

Tabla 1 Tiempos promedio de la ejecución de la Mochila Binaria Iterativa

Mochila Iterativa
N 0 10 50 100 250 500 750 1000
t [ms] 0 0.0751 0.136 0.2229 0.5286 1.0613 1.6892 2.2851

Posterior a esto se procedió a graficar los datos para así poder realizar un ajuste lineal, esto
debido a que se sabe que la complejidad del algoritmo es de orden 1, obteniendo la Fig. 1 y así
obtener el valor de la constante de proporcionalidad correspondiente.

Mochila Iterativa
2.5
2
1.5
t[ms]

1
0.5
0
0 200 400 600 800 1000 1200
Número de elementos

Figura 1 Tendencia temporal Mochila Binaria Iterativa

Del ajuste lineal realizado a los datos, se obtuvo la ecuación que describe el comportamiento
temporal del algoritmo (Ec. 9) con la cual se puede predecir el tiempo que tomará el programa
en ejecutarse con instancias mayores a las utilizadas.

𝑦 = 0.0022𝑥 (9)

2.2.2. Algoritmo Mochila Binaria.

En el Apéndice 2 se encuentra el código escrito en lenguaje Java para la solución al problema de
la Mochila Binaria con la técnica de programación dinámica implementada.

Al igual que en el caso anterior, se obtuvieron 5 tiempos con la finalidad de obtener un

promedio de los tiempos de ejecución para los mismos tamaños de instancias (Tabla 2).

Tabla 2 Tiempos promedio de la ejecución de la Mochila Binaria PD

Mochila Binaria
N 0 10 50 100 250 500 750 1000
t [ms] 0 0.0626 0.1056 0.2212 0.54 1.2287 1.5569 2.3198

Con estos datos, se procedió a realizar un gráfico (Figura 2) para poder realizar un ajuste
dependiendo a la tendencia de éstos, correspondiendo a un ajuste lineal (polinomio de grado 1).

Mochila Binaria
2.5

1.5
t[ms]

0.5

0
0 200 400 600 800 1000 1200
Número de elementos

Figura 2 Tendencia temporal Mochila Binaria PD

La ecuación (10) corresponde a la ecuación obtenida del ajuste realizado anteriormente.
𝑦 = 0.0023𝑥 (10)

3. DISCUSIÓN.

En la Figura 3, se muestran las tendencias de los dos algoritmos propuestos y utilizando el

tamaño de las instancias 𝑛 = 10, 50, 100, 250, 500, 750 y 1000.
De esta manera se puede apreciar de mejor manera que ambos algoritmos tienen una
complejidad temporal correspondiente a la de un polinomio de primer grado.

Tendencia temporal
2.5

1.5
Mochila Iterativa
t[ms]

Mochila Binaria
1
Lineal (Mochila Iterativa)

0.5 Lineal (Mochila Binaria)

0
0 200 400 600 800 1000 1200
Número de elementos

Figura 3 Tendencia temporal Mochila Binaria Iterativa y PD

Con las ecuaciones obtenidas de los ajustes, se realizó una predicción del tiempo de ejecución en
milisegundos para instancias de tamaño 𝑛 = 10000, 100000 y 1000000. Los resultados se
muestran en la tabla 3.

Tabla 3 Tiempo [ms] estimado de ejecución para instancias de mayor tamaño

Iterativa Binaria
N t[ms]
10000 22 23
100000 220 230
1000000 2200 2300
De esto, se puede observar que el algoritmo con la programación dinámica implementada toma
1 ms más en realizar el cálculo, esto se puede atribuir al hecho de que le toma más tiempo
guardar el valor de las combinaciones durante su ejecución

4. CONCLUSIÓN

Se cumplieron con los objetivos establecidos. Se pudo desarrollar dos códigos sin errores de
sintaxis que dieran solución al planteamiento del problema de la Mochila Binaria, uno tradicional
y otro con la técnica de programación dinámica implementada.

Se logró obtener los tiempos de ejecución para las instancias de diversos tamaños para
luego determinar las constantes que completan y modelan la ecuación polinomial de primer
orden y, de esa manera, poder hacer predicciones de los tiempos de ejecución para instancias de
mayores tamaños al de las utilizadas durante el análisis.

El desempeño de ambos métodos es el esperado ya que ambos respetan la complejidad temporal

lineal que también depende del valor asociado a la capacidad del contenedor.
Bibliografía

 Gilles Brassard, Paul Bratley, Fundamental of Algorithmics, Prentice Hall. 1996.

 Velasco, J. (2010). NP-Completeness: Universidad Autónoma de Nuevo León Facultad de
Ingeniería Mecánica y Eléctrica División de Posgrado en Ingeniería de Sistemas. (s/f).
Docplayer.Es. Recuperado de https://docplayer.es/36570933-Np-completeness-
universidad-autonoma-de-nuevo-leon-facultad-de-ingenieria-mecanica-y-electrica-
division-de-posgrado-en-ingenieria-de-sistemas.html
 Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms
(3rd Edition). MIT Press. https://pd.daffodilvarsity.edu.bd/course/material/book-
430/pdf_content
 Gómez Fuentes, M. del C., & Cervantes Ojeda, J. (2014). Introducción al Análisis y al
Diseño de Algoritmos (Primera). María del Carmen Gómez Fuentes, Jorge Cervantes
Ojeda.
https://www.cua.uam.mx/pdfs/conoce/libroselec/Notas_Analisis_AlgoritmosVF.pdf
 Fernández, L. L. (s/f). Introducción a la programación dinámica. Usc.es. Recuperado de
https://minerva.usc.es/xmlui/bitstream/handle/10347/28920/López_Fernández_Lidia.
pdf?sequence=1&isAllowed=y#:~:text=La%20programación%20dinámica%20es%20un,
para%20el%20proble-%20ma%20original
 Flores, I. (s/f). Programación Dinámica. Unam.mx. Recuperado el 8 de noviembre de
2023, de
https://www.ingenieria.unam.mx/sistemas/PDF/Avisos/Seminarios/SeminarioV/Sesion
6_IdaliaFlores_20abr15.pdf
 Cerinza, N. G. (s/f). FAEDIS. Edu.co. Recuperado el 8 de noviembre de 2023, de
http://virtual.umng.edu.co/distancia/ecosistema/odin/odin_desktop.php?path=Li4vb3
Zhcy9pbmdlbmllcmlhX2NpdmlsL2ludmVzdGlnYWNpb25fZGVfb3BlcmFjaW9uZXNfaWkv
dW5pZGFkXzQv
 Introduction to Knapsack Problem, its Types and How to solve them. (2023, abril 6).
GeeksforGeeks. https://www.geeksforgeeks.org/introduction-to-knapsack-problem-its-
BUAP-FCC Análisis y Diseño de Algoritmos

types-and-how-to-solve-them/
 0/1 knapsack problem. (2012, marzo 19). GeeksforGeeks.
https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
 Martínez, A. Algoritmos y Programación II Técnicas Avanzadas de Diseño de Algoritmos
(Programación Dinámica) (S/f). Studocu.com. Recuperado de:
https://www.studocu.com/latam/document/universidad-de-
carabobo/algoritmos/programacion-dinamica-teoria/36386431

17
BUAP-FCC Análisis y Diseño de Algoritmos

Apéndice

Apéndice 1: Código de la mochila iterativa para datos ordenados de manera aleatoria.

import java.util.Random;

public class MochilaIterativa {

// Función para resolver el problema de la mochila iterativa

public static int mochilaIterativa(int capacidad, int[] pesos, int[]
valores) {
int n = pesos.length;

int[][] matrizResultados = new int[n + 1][capacidad + 1];

for (int i = 0; i <= n; i++) {

for (int w = 0; w <= capacidad; w++) {
if (i == 0 || w == 0) {
matrizResultados[i][w] = 0;
} else if (pesos[i - 1] <= w) {
matrizResultados[i][w] = Math.max(valores[i - 1] +
matrizResultados[i - 1][w - pesos[i - 1]],
matrizResultados[i - 1][w]);
} else {
matrizResultados[i][w] = matrizResultados[i -
1][w];
}
}
}

return matrizResultados[n][capacidad];
}

// Función para generar una instancia aleatoria de tamaño N

public static int[][] generateRandomInstance(int N) {
int[] pesos = new int[N];
int[] valores = new int[N];
Random random = new Random();
for (int i = 0; i < N; i++) {
pesos[i] = random.nextInt(20) + 1; // Pesos entre 1 y 20

18
BUAP-FCC Análisis y Diseño de Algoritmos

valores[i] = random.nextInt(50) + 1; // Valores entre 1 y 50

}
return new int[][]{pesos, valores};
}

// Función para medir el tiempo de procesamiento

public static double measureTime(int capacidad, int[] pesos, int[]
valores) {
long startTime = System.nanoTime();
mochilaIterativa(capacidad, pesos, valores);
long endTime = System.nanoTime();

// Calcular el tiempo en nanosegundos y convertirlo a

milisegundos
double tiempoEnNanosegundos = endTime - startTime;
double tiempoEnMilisegundos = tiempoEnNanosegundos /
1_000_000.0;

return tiempoEnMilisegundos;
}

public static void main(String[] args) {

// Tamaños de instancia
int[] tamañosInstancia = {10, 50, 100, 250, 500, 750, 1000,
4000};

for (int N : tamañosInstancia) {

int[][] instancia = generateRandomInstance(N);
int capacidad = N * 10; // Ajusta la capacidad según tu
escenario

// Medir el tiempo de procesamiento para cada instancia

double tiempoEnMilisegundos = measureTime(capacidad,
instancia[0], instancia[1]);
System.out.println("Tamaño N=" + N + ", Tiempo=" +
tiempoEnMilisegundos + " ms");
}
}
}

19
BUAP-FCC Análisis y Diseño de Algoritmos

Apéndice 1.1: Código de la mochila iterativa para datos ordenados de manera aleatoria (impresión de
pantalla).

20
BUAP-FCC Análisis y Diseño de Algoritmos

Apéndice 2: Código del método de la Mochila Binaria usando programación dinámica para datos ordenados
de manera aleatoria.

import java.util.Random;

public class MochilaBinariaDinamica {

// Función para resolver el problema de la mochila binaria con

programacion dinamica
public static int mochila01(int[] pesos, int[] valores, int
capacidad) {
int n = pesos.length;
int[][] matriz = new int[n + 1][capacidad + 1];

for (int i = 0; i <= n; i++) {

for (int w = 0; w <= capacidad; w++) {
if (i == 0 || w == 0) {
matriz[i][w] = 0;
} else if (pesos[i - 1] <= w) {
matriz[i][w] = Math.max(matriz[i - 1][w], valores[i
- 1] + matriz[i - 1][w - pesos[i - 1]]);
} else {
matriz[i][w] = matriz[i - 1][w];
}
}
}

return matriz[n][capacidad];
}

public static double measureTime(int capacidad, int[] pesos, int[]

valores) {
long startTime = System.nanoTime();
mochila01(pesos, valores, capacidad);
long endTime = System.nanoTime();

double tiempoEnNanosegundos = endTime - startTime;

double tiempoEnMilisegundos = tiempoEnNanosegundos /
1_000_000.0;

return tiempoEnMilisegundos;

21
BUAP-FCC Análisis y Diseño de Algoritmos

public static int[][] generateRandomInstance(int N) {

int[] pesos = new int[N];
int[] valores = new int[N];
Random random = new Random();
for (int i = 0; i < N; i++) {
pesos[i] = random.nextInt(20) + 1;
valores[i] = random.nextInt(50) + 1;
}
return new int[][]{pesos, valores};
}

public static void main(String[] args) {

int[] tamañosInstancia = {10, 50, 100, 250, 500, 750, 1000,
4000};

for (int N : tamañosInstancia) {

int[][] instancia = generateRandomInstance(N);
int capacidad = N * 10;

double tiempoEnMilisegundos = measureTime(capacidad,

instancia[0], instancia[1]);
System.out.println("Tamaño N=" + N + ", Tiempo=" +
tiempoEnMilisegundos + " ms");
}
}
}

Apéndice 2.1: Código de la Mochila Binaria para datos ordenados de manera aleatoria (impresión de
pantalla).

22