Otimização do problema da mochila 0-1
uma abordagem baseada em programação dinâmica para seleção de itens com restrição de capacidade
DOI:
https://doi.org/10.47385/tudoeciencia.2568.2025Palavras-chave:
Programação dinâmica. Problema da mochila. Otimização combinatória. Algoritmos de aproximação. Análise de eficiência.Resumo
Este trabalho apresenta uma implementação e análise do algoritmo clássico de programação dinâmica aplicado ao Problema da Mochila 0-1 (Knapsack Problem), utilizando um conjunto de sete itens eletrônicos com diferentes valores monetários e pesos físicos. O estudo investigou a eficácia da abordagem de programação dinâmica na otimização da seleção de itens sob restrição de capacidade de 5 kg, maximizando o valor total transportado. Os resultados demonstraram que o algoritmo selecionou três itens (Câmera, Tablet e Smartphone) com valor total de R$ 6.000,00, utilizando integralmente a capacidade disponível e alcançando uma eficiência de 1.200,00 R$/kg. A análise comparativa entre itens selecionados e não selecionados revelou que o algoritmo priorizou adequadamente a relação valor-peso, excluindo o Notebook apesar de seu alto valor individual (R$ 3.000,00) devido ao seu peso excessivo. A visualização gráfica dos resultados confirmou a distribuição otimizada dos recursos, demonstrando a aplicabilidade prática do método em problemas de otimização combinatória.
Downloads
Referências
BALAS, E.; ZEMEL, E. An algorithm for large zero-one knapsack problems. Operations Research, v. 28, n. 5, p. 1130-1154, 1980.
BELLMAN, R. Dynamic Programming. Princeton: Princeton University Press, 1957.
MORIMOTO, Naoyuki. Power allocation optimization as the multiple knapsack problem with assignment restrictions. In: 2017 8th International Conference on the Network of the Future (NOF). IEEE, 2017. p. 40-45.
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009.
DANTZIG, G. B. Discrete-variable extremum problems. Operations Research, v. 5, n. 2, p. 266-277, 1957.
GAREY, M. R.; JOHNSON, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1990.
HOROWITZ, E.; SAHNI, S. Computing partitions with applications to the knapsack problem. Journal of the ACM, v. 21, n. 2, p. 277-292, 1974.
KELLERER, Hans; PFERSCHY, Ulrich; PISINGER, David. Multidimensional knapsack problems. In: Knapsack problems. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. p. 235-283.
KLEINBERG, J.; TARDOS, E. Algorithm Design. Boston: Addison-Wesley, 2005.
MARTELLO, S.; TOTH, P. Knapsack Problems: Algorithms and Computer Implementations. Chichester: John Wiley & Sons, 1990.
NEMHAUSER, G. L.; ULLMANN, Z. Discrete dynamic programming and capital allocation. Management Science, v. 15, n. 9, p. 494-505, 1969.
PISINGER, D. A minimal algorithm for the 0-1 knapsack problem. Operations Research, v. 45, n. 5, p. 758-767, 1997.
SEDGEWICK, R.; WAYNE, K. Algorithms. 4. ed. Boston: Addison-Wesley, 2011.
TOTH, P.; VIGO, D. Vehicle Routing: Problems, Methods, and Applications. 2. ed. Philadelphia: SIAM, 2014.
VAZIRANI, V. V. Approximation Algorithms. Berlin: Springer-Verlag, 2003.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2025 Tudo é Ciência: Congresso Brasileiro de Ciências e Saberes Multidisciplinares
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
