Programação Dinâmica – problema da Mochila 0-1 ou 0-1 Knapsack

Olá pessoal,

Dando continuidade ao estudo de programação dinâmica preparei mais uma aplicativo. Desta vez para solucionar o problema da Mochila 0-1 (binária) ou 0-1 Knapsack.

Enunciado do problema:

Um ladrão que rouba uma loja encontra n objetos. Cada objeto tem valor v e peso p.
O ladrão tem uma mochila que aguenta peso W e quer levar a carga roubada mais valiosa possível.

Esse problema pode ser tratado como da classe NP-completo ou NP-hard dependendo a forma de abordagem.

Segundo minha pesquisa, quando resolvido com programação dinâmica ele tempo pseudo-polinomial. Isso quer dizer que seu tempo de execução é polinomial em função do valor numérico da entrada, porém é exponencial no comprimento da entrada (o número de bits necessários para representá-la).

Montei uma aplicação para testar minha solução com programação dinâmica. Para ser sincero, esse problema me custou muitas horas de trabalho… mas enfim funcionou.

O código foi todo escrito em C# e deixei um botão para você poder copiar os métodos utilizados.

A figura abaixo ilustra o aplicativo, que está disponível no Dropbox. Basta clicar na imagem para ser redirecionado.

ProgramacaoDinamica_Mochila_0_1

Programação Dinâmica: Problema da Mochila 0-1

Se preferir, pode baixar todo o código fonte clicando aqui.

Observação: Quando rodar, perceba que na tabela inferior estão todas a subsoluções ótimas de acordo com o peso máximo da mochila. Os itens marcados com asterisco são os utilizados na solução ótima para o peso máximo definido.

Esse aplicativo foi desenvolvido como atividade complementar e voluntária do meu curso de doutorado, minha única intenção é compartilhar conhecimento.

Espero que gostem!

Um abraço,

Prof. Leandro

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: