A continuación, veremos un programa en Excel VBA ese resuelve una pequeña instancia de un problema de la mochila.
Definición: Dado un conjunto de elementos, cada uno con un peso y un valor, determine los elementos que se incluirán en una colección para que el valor total sea lo más grande posible y el peso total sea menor que un límite dado. Deriva su nombre del problema al que se enfrenta alguien que está limitado por una mochila de tamaño fijo y debe llenarla con los artículos más útiles.
Ejemplo: 5 elementos 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 Double con nombres limit, weight, value, totalWeight y maximumValue.
Límite de atenuación como doble, peso como doble, valor como doble, peso total como doble, valor máximo como doble
2. A continuación, declaramos cinco variables de tipo Integer 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 valor 0.
límite = Rango ("D6"). valor
maximumValue = 0
4. A continuación, comprobamos cada una de las posibles soluciones. Podemos incluir un elemento (1) o dejarlo fuera (0). Comenzamos 5 bucles For Next. Uno para cada artículo.
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. Solo si el valor es mayor que maximumValue y el peso es menor que el límite, hemos encontrado una nueva solución mejor.
Si valor> valor máximo y peso <= límite Entonces
7. Si es verdadero, escribimos la nueva solución en la fila 4, ponderación en peso total y valor en valor máximo.
Rango ("B4"). Valor = i
Rango ("C4"). Valor = j
Rango ("D4"). Valor = k
Rango ("E4"). Valor = l
Rango ("F4"). Valor = m
totalWeight = peso
maximumValue = valor
8. No olvide cerrar la declaración If.
Terminara si
9. No olvide cerrar los bucles 5 For Next.
Siguiente m
Siguiente l
Siguiente k
Siguiente j
Siguiente yo
Excel VBA verifica cada solución posible 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 totalWeight y maximumValue de la solución óptima en las celdas B6 y B8 respectivamente.
Rango ("B6"). Valor = peso total
Rango ("B8"). Valor = valor máximo
11. Pruebe el programa.
Resultado:
Conclusión: es óptimo incluir los últimos cuatro ítems con un valor máximo de 15. Esta solución con un peso total de 2 + 1 + 1 + 4 = 8 no excede el límite de 15.
Nota: al hacer variables los pesos y valores, puede resolver cualquier problema de mochila de este tamaño (ver archivo Excel descargable).
