Abaixo, veremos um programa em Excel VBA que resolve uma pequena instância de um problema de mochila.
Definição: Dado um conjunto de itens, cada um com um peso e um valor, determine os itens a serem incluídos em uma coleção de forma que o valor total seja o maior possível e o peso total seja menor que um determinado limite. Seu nome deriva do problema enfrentado por alguém que é restringido por uma mochila de tamanho fixo e deve enchê-la com os itens mais úteis.
Exemplo: 5 itens com pesos, valores e limite conforme fornecidos.
No Excel, esse problema é o seguinte:
1. Primeiro, declaramos cinco variáveis do tipo Double com os nomes limit, weight, value, totalWeight e maximumValue.
Dim limit As Double, weight As Double, value As Double, totalWeight As Double, maximumValue As Double
2. Em seguida, declaramos cinco variáveis do tipo Inteiro com nomes i, j, k, l, m.
Dim i, j, k, l, m como inteiro
3. Inicializamos duas variáveis. Inicializamos o limite da variável com o valor da célula D6. Inicializamos a variável maximumValue com valor 0.
limite = intervalo ("D6"). valor
maximumValue = 0
4. A seguir, verificamos cada solução possível. Podemos incluir um item (1) ou omitir (0). Começamos 5 loops For Next. Um para cada item.
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 o peso e o valor de uma possível solução.
peso = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
valor = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Somente se o valor for maior que o valor máximo e o peso for menor que o limite, encontramos uma nova solução melhor.
Se valor> valor máximo e peso <= limite Então
7. Se verdadeiro, escrevemos a nova solução na linha 4, peso em peso total e valor em valor máximo.
Intervalo ("B4"). Valor = i
Intervalo ("C4"). Valor = j
Intervalo ("D4"). Valor = k
Intervalo ("E4"). Valor = l
Intervalo ("F4"). Valor = m
totalWeight = peso
maximumValue = value
8. Não se esqueça de fechar a instrução If.
Fim se
9. Não se esqueça de fechar os loops 5 For Next.
Próximo m
Próximo l
Próximo k
Próximo j
Proximo eu
O Excel VBA verifica cada solução possível dessa maneira e, como resultado, a solução ideal aparecerá na linha 4. Lembre-se, 1 significa que incluímos um item, 0 significa que o deixamos de fora.
10. Finalmente, escreva totalWeight e maximumValue da solução ótima para as células B6 e B8, respectivamente.
Intervalo ("B6"). Valor = peso total
Intervalo ("B8"). Valor = valor máximo
11. Teste o programa.
Resultado:
Conclusão: o ideal é incluir os quatro últimos itens com valor máximo de 15. Esta solução com peso total de 2 + 1 + 1 + 4 = 8 não ultrapassa o limite de 15.
Nota: ao tornar os pesos e valores variáveis você pode resolver qualquer problema de mochila deste tamanho (veja arquivo Excel para download).
