O problema da mochila é um problema de otimização combinatória. Isto que dizer que temos que trabalhar com diversas combinações e obter uma combinação que é ótima, ou seja, é a melhor segundo algum critério. O problema da mochila é um dos 21 problemas NP-completos de Richard Karp.
Este tipo de problema queremos preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é preencher a mochila com o maior valor possível, contudo não podemos ultrapassar o peso máximo. Vemos portanto que formulação do problema é extremamente simples, porém sua solução é mais complexa.
No vídeo apresentamos como resolver esta versão da mochila.
Existem diversas variações do problema da mochila. Se você estiver curioso dê uma olhada na wikipedia.
Nenhum comentário:
Postar um comentário