ABORDAGENS PARA RESOLVER O PROBLEMA DA MOCHILA 0/1
Barra lateral de artigos
Conteúdo do artigo principal
Resumo
O propósito deste artigo é apresentar quatro abordagens para resolver problemas de otimização combinatória, aplicando-as ao Problema da Mochila 0/1. As técnicas e os algoritmos usados para resolver o Problema da Mochila 0/1 foram: Força Bruta, Programação Dinâmica, Algoritmo Gu- loso e Branch and Bound. Um comparativo da complexidade de tempo de execução assintótico, do tempo de execução de máquina, da memória requerida e do esforço de programação necessário para cada algoritmo formulado como solução também é apresentado.
Detalhes do artigo
Referências
Chinneck, J.W., (2007). “Practical Optimiza- tion: A Gentle Introduction”, http://www.sce.
carleton.ca/faculty/chinneck/po.html.
Cormen H. (2002). “Introduction to Algori- thms”. Second Edition.
Goldbarg, M. e Luna, H. (2005). Otimização Combinatória e Programação Linear: Modelos e Algoritmos”. 2ª Edição.
Hristakeva, M. e Shrestha, D. (2005). “Diffe- rent Approaches to Solve the 0/1 Knapsack Problem”. Editora Campus., Rio de Janeiro.
Land, A.H. and Doig, A.G. (1960). “An auto- matic method for solving discrete programming problems” Econometrica, 28, Julho, Number 3.
Martello, Silvano e Toth, P. (1990). “Knapsack Problems – Algorithms and Computer Imple- mentations”, John Wiley & Sons ltd., England.
Pisinger, D. (1993). “An expanding-core algo- rithm for exact 0-1 Knapsack Problem”. Euro- pean Journal of Operational Research, 87:175- 187, 1995.
Ziviani, N. (2006). “Projeto de Algoritmos com implementações em Java e C++”, Thomson Learning. Primeira Edição.