Problema da mochila

TRABALHO PRÁTICO – PROBLEMA DA MOCHILA
MOCHILA FRACIONÁRIA E BOOLEANA

Aluno: Alex Leite Chagas
Campus Belo Horizonte – Núcleo Universitário Contagem
Curso: Sistemas de Informação – Noite – 3º Período
Disciplina: Laboratório da Computação 3
Professor: Gustavo da Gama Torres

TRABALHO PRÁTICO – PROBLEMA DA MOCHILA
MOCHILA FRACIONÁRIA E BOOLEANA
ALEX LEITE CHAGAS

Campus Belo Horizonte – Núcleo Universitário Contagem
Curso: Sistemas de Informação – Noite – 3º Período
Disciplina: Laboratório de Computação 3
Professor: Gustavo da Gama Torres
SUMÁRIO
Introdução ....................................................................................... 4
Técnicas Utilizadas.......................................................................... 5 Programação Dinâmica.......................................................... 5 Programação Gulosa.............................................................. 5
Desenvolvimento do Trabalho......................................................... 6
Métodos Implementados ................................................................. 7
Complexidade dos Algoritmos ....................................................... 10
Conclusão ...................................................................................... 11

INTRODUÇÃO
O problema da mochila é um problema de otimização combinatória. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo. Este trabalho se aplica sobre a resolução do problema da mochila com o algoritmo guloso e algoritmo de programação dinâmica, os quais serão explicados e demonstrados ao decorrer do trabalho.

TÉCNICAS UTILIZADAS
O programa desenvolvido apresenta a seguintes técnicas de programação dinâmica e gulosa.

Programação dinâmica No trabalho a programação dinâmica foi utilizada no