Problema da Mochila Multidimensional com Pogramação Dinâmica

Abstract

O problema da mochila 0-1 é um problema NP-Completo, composto por uma mochila contendo uma capacidade W, uma entrada de n itens, cada um com um valor p e um peso w. A maximização deste problema retorna um conjunto X de itens que formam o resultado com o valor máximo. Uma extensão da mochila 0-1 é a mochila multidimensional, que possui mais de uma capacidade para a mochila e, utilizando paralelismo junto com um algoritmo exato da mochila 0-1, podemos fazer uma adaptação para o problema da mochila de 2 dimensões, assim encontramos a resposta para este problema utilizando menos espaço para o cálculo.