A continuación veremos un programa en Excel VBA que resuelve una pequeña instancia de un problema de mochila .
Definición: Dada una serie de artículos, cada uno con un peso y un valor, determinar los artículos a incluir en una colección de manera que el valor total sea lo más grande posible y el peso total sea menor que un límite determinado. Recibe su nombre del problema que enfrenta alguien que está limitado por una mochila de tamaño fijo y debe llenarla con los artículos más útiles.
Ejemplo: 5 artículos con pesos, valores y límite como se indica.
En Excel este problema se ve de la siguiente manera:
1. Primero, declaramos cinco variables de tipo Doble con nombres límite, peso, valor, totalPeso y máximoValor.
Límite Dim como doble, peso como doble, valor como doble, totalPeso como doble, máximoValor como doble
2. A continuación, declaramos cinco variables de tipo Entero con nombres i, j, k, l, m.
Dim i, j, k, l, m como entero
3. Inicializamos dos variables. Inicializamos el límite de la variable con el valor de la celda D6. Inicializamos la variable maximumValue con el valor 0.
límite = Rango(«D6»).valor Valor máximo = 0
4. A continuación, comprobamos cada posible solución. Podemos incluir un elemento (1) o dejarlo fuera (0). Empezamos con 5 para los siguientes bucles. Uno para cada elemento.
Para i = 0 a 1 Para j = 0 a 1 Para k = 0 a 1 Para l = 0 a 1 Para m = 0 a 1
5. Calculamos el peso y el valor de una posible solución.
peso = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m valor = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Sólo si el valor es mayor que el valor máximo y el peso es menor que el límite, hemos encontrado una nueva solución mejor.
Si valor; máximoValor Y peso <= límite Entonces
7. Si es cierto, escribimos la nueva solución en la fila 4, el peso al peso total y el valor al valor máximo.
Rango(«B4»).valor = i Rango(«C4»).valor = j Rango(«D4»).valor = k Rango(«E4»).valor = l Rango(«F4»).valor = m totalPeso = peso maximumValue = valor
8. No te olvides de cerrar la declaración de Si.
Finalizar si
9. No te olvides de cerrar los 5 bucles de «For Next».
El siguiente m Siguiente. Siguiente k Siguiente j Siguiente…
El Excel VBA comprueba cada posible solución de esta manera y como resultado la solución óptima aparecerá en la fila 4. Recuerde, 1 significa que incluimos un elemento, 0 significa que lo dejamos fuera.
10. Finalmente, escriba el peso total y el valor máximo de la solución óptima en la celda B6 y B8 respectivamente.
Rango(«B6»).valor = totalPeso Rango(«B8»).value = maximumValue
11. Pruebe el programa.
Resultado:
Conclusión: es óptimo incluir los últimos cuatro elementos con un valor máximo de 15. Esta solución con un peso total de 2 + 1 + 1 + 4 = 8 no supera el límite de 15.
Nota: haciendo que los pesos y valores sean variables se puede resolver cualquier problema de mochila de este tamaño (ver archivo de Excel descargable).