A continuación, veremos un programa en Excel VBA que resuelve una pequeña instancia de un problema de 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.

Dim limit As Double, weight As Double, value As Double, totalWeight As Double, maximumValue As Double

2. A continuación, declaramos cinco variables de tipo Integer con nombres i, j, k, l, m.

Dim i, j, k, l, m As Integer

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.

limit = Range("D6").value
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.

For i = 0 To 1
    For j = 0 To 1
        For k = 0 To 1
            For l = 0 To 1
                For m = 0 To 1

5. Calculamos el peso y el valor de una posible solución.

weight = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
value = 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.

If value > maximumValue And weight <= limit Then

7. Si es verdadero, escribimos la nueva solución en la fila 4, ponderación en peso total y valor en valor máximo.

Range("B4").value = i
Range("C4").value = j
Range("D4").value = k
Range("E4").value = l
Range("F4").value = m
totalWeight = weight
maximumValue = value

8. No olvide cerrar la declaración If.

End If

9. No olvide cerrar los bucles 5 For Next.

                Next m
            Next l
        Next k
    Next j
Next i

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. Por último, escriba totalWeight y maximumValue de la solución óptima en las celdas B6 y B8, respectivamente.

Range("B6").value = totalWeight
Range("B8").value = maximumValue

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).

11/11 Completado! Obtenga más información sobre los bucles>
Capítulo siguiente: Errores de macro