problema da mochila
1188 palavras
5 páginas
UNIVERSIDADE FEDERAL DO ESPIRITO SANTOCURSO DE CIÊNCIA DA COMPUTAÇÃO
DISCIPLINA: TEORIA DOS GRAFOS
PROBLEMA DA MOCHILA, UMA ABORDAGEM UTILIZANDO BACKTRACKING
ESPIRITO SANTO
2013
GILBERTO EWALD FILHO MATEUS OLIVEIRA ALMEIDA THIAGO SALVATORE
PROBLEMA DA MOCHILA, UMA ABORDAGEM UTILIZANDO BACKTRACKING
Trabalho apresentado a disciplina de Teoria dos grafos
Professor: Saulo Bortolon
ESPIRITO SANTO
2013
Sumário
1. INTRODUÇÃO 4
2. UMA ABORDAGEM PARA O PROBLEMA 6
3. BACKTRACKING 9 3.1 EXEMPLO DE ALGORITMO BACKTRACKING 11
4. RESOLVENDO O PROBLEMA DA MOCHILA COM BACKTRACKING 14
5. IMPLEMENTAÇÃO EM C PARA O PROBLEMA DA MOCHILA UTILIZANDO BACKTRACKING......................................................18
6. REFERÊNCIAS BIBLIOGRÁFICAS 21
1. INTRODUÇÃO
O problema da mochila (Knapsack problema, em inglês), pertence a uma classe de problemas dos mais conhecidos e mais estudos na área da ciência da computação, em particular em otimização combinatória.
Mas antes vamos definir o que é um problema combinatório. Podemos definir problema combinatório por uma coleção finita de objetos que satisfaçam um critério específico, que pode ser uma regra ou restrição.
Algumas características dos problemas combinatórios é que podem ser feitas de diferentes objetos a satisfazer o problema, também é possível enumerar as escolhas para os objetos e são compostas pelas combinações de objetos a partir de um conjunto de possibilidades.
O problema da mochila é um dos 21 problemas NP-completos. A definição formal de NP-completude, é que um problema X é completo em NP, ou NP-completo, se X está em NP e todos os demais problemas em NP não são mais difíceis que X.
O problema da mochila se resume na situação em que precisamos preencher uma mochila de objetos a fim de obter a maior soma dos