7. Além do uso de programação dinâmica, o problema da mochila pode ser resolvido, obtendo o valor 6timo, utilizando também divisão e conquista e força bruta. Essas abordagens, porém, possuem complexidade exponencial e são menos eficientes quando comparado com a programação dinâmica. Pesquise sobre como responder o problema da mochila usando divisão e conquista, destacando todas as etapas da solução proposta, referente a passo base e ao passo recursivo (divisão, conquista e combinação). Indique ainda a recorrência e a complexidade encontrada.

Para resolver o problema da mochila usando a abordagem de divisão e conquista, podemos seguir os seguintes passos:<br /><br />Passo base:<br />O passo base da abordagem de divisão e conquista é quando temos um subproblema que pode ser resolvido diretamente, sem a necessidade de mais divisões. Nesse caso, o subproblema é quando temos apenas um item na mochila e precisamos determinar se ele deve ser incluído ou não.<br /><br />Passo recursivo (divisão, conquista e combinação):<br />1. Divisão: Dividimos o problema em subproblemas menores. Nesse caso, dividimos o conjunto de itens em dois conjuntos: um com os itens que podem ser carregados e outro com os itens que não podem ser carregados.<br />2. Conquista: Resolvemos cada subproblema de forma independente. Para cada subproblema, determinamos se os itens podem ser carregados ou não, considerando o peso e o valor de cada item, bem como o limite de peso da mochila.<br />3. Combinação: Após resolver cada subproblema, combinamos os resultados para encontrar a solução final. Nesse caso, devemos considerar todas as combinações possíveis de itens que podem ser carregados na mochila, considerando o limite de peso.<br /><br />A recorrência ocorre quando aplicamos o algoritmo de divisão e conquista para resolver cada subproblema, até que cheguemos ao passo base.<br /><br />A complexidade do algoritmo de divisão e conquista para resolver o problema da mochila é O(n log n), onde n é o número de itens. Isso ocorre porque cada etapa de divisão reduz o tamanho do problema em fatores, até que cheguemos ao passo base. No entanto, é importante ressaltar que essa abordagem é menos eficiente do que a programação dinâmica, devido à sua complexidade exponencial.