Neste trabalho, ser ́a estudado um famoso problema de otimização combina conhecido como Problema da Mochila. O problema ́e integrante da classe NP-dif ́e pode ser enunciado considerando uma situação onde ́e necessário carregar uma mochila contendo um conjunto de objetos de pesos e valores diferentes. Logo, essa mochila possui capacidade limitada e deve ser maximizado o valor total, fazendo com o que os objetos n ̃ao ultrapassemo limite da mochila. A metodologia proposta envolve a solução através de uma heurística e uma meta heurística, sendo os Algoritmos Gulosos e o VNS,respectivamente e uma solução exata utilizando a Programação Dinâmica. O problema da Mochila possui aplicações muito conhecidas, como em problemas de embalagem, de carregamento de equipamentos, de corte de materiais, de controle orçamental e de seleção de projetos de investimento.
