Definição – o que significa problema da mochila?
O problema da mochila é um problema de otimização usado para ilustrar o problema e a solução. Seu nome deriva de um cenário em que o número de itens que podem ser colocados dentro de uma mochila de tamanho fixo é limitado. Dado um conjunto de itens com pesos e valores específicos, o objetivo é colocar o máximo de valor possível na mochila, dada a restrição de peso da mochila.
Definirtec explica o problema da mochila
O problema da mochila é um exemplo de um problema de otimização combinacional, um tópico em matemática e ciência da computação sobre como encontrar o objeto ideal entre um conjunto de objetos. Este é um problema que vem sendo estudado há mais de um século e é um problema de exemplo comumente usado em otimização combinatória, onde há a necessidade de um objeto ótimo ou solução finita onde uma busca exaustiva não é possível. O problema pode ser encontrado em cenários do mundo real, como alocação de recursos em restrições financeiras ou mesmo na seleção de investimentos e carteiras. Também pode ser encontrado em áreas como matemática aplicada, teoria da complexidade, criptografia, combinatória e ciência da computação. É facilmente o problema mais importante em logística.
No problema da mochila, os itens dados têm dois atributos no mínimo – o valor de um item, que afeta sua importância, e o peso ou volume de um item, que é seu aspecto de limitação. Visto que uma busca exaustiva não é possível, pode-se dividir os problemas em subproblemas menores e executá-los recursivamente. Isso é chamado de subestrutura ótima. Trata-se de apenas um item de cada vez e o peso atual ainda está disponível na mochila. O solucionador de problemas só precisa decidir se leva ou não o item com base no peso que ainda pode ser aceito. No entanto, se for um programa, o recálculo não é independente e causaria problemas. É aqui que as técnicas de programação dinâmica podem ser aplicadas. As soluções para cada subproblema são armazenadas de forma que o cálculo só precise acontecer uma vez.