Portal de Periódicos da CAPES

APLICAÇÃO DO PARADIGAMA “DIVIDIR E CONQUISTAR” PARA RESOLUÇÃO DO PROBLEMA DA MOCHILA

2023; Linguagem: Inglês

10.29327/conemi23.672361

2764-4294

Wilson Garcia Guibor,

Academic Research in Diverse Fields

The knapsack problem is a topic widely studied in academia, especially in the field of combinatorial optimization, and has many practical applications in real-world scenarios, such as capital investment, cutting and packing, vehicle loading, load sizing and resource allocation., between others.Although it is popular and apparently easy to understand, the solution to this problem can become complex, especially when the number of variables increases.In real contexts, problems tend to be extensive and intricate, which drives the search for alternatives that provide simpler, more efficient and less complex solutions.In this context, the Divide and Conquer paradigm emerges as a didactic approach to finding solutions to large and complex problems, by solving them by solving smaller and simpler subproblems.This work presents a study, implementation and analysis of two solution methods -Divide and Conquer and Dynamic Programming -for the knapsack problem in different sizes (S, M, L and XL), and compares them with the greedy heuristic.The implementation of the algorithms was carried out using the C Programming Language.The comparative analysis of these methods aims to identify their advantages and disadvantages in terms of efficiency and accuracy in solving the knapsack problem in different scenarios.