Problema da mochila: diferenças entre revisões

Por ser um problema combinatório é possível resolveresolvê-lo por enumeração exaustiva, ou seja tentar todas as soluções possíveis e comparando-as para identificar a melhor solução. Porém, isso se torna completamente inviável uma vez quepois, mesmo em pequenas dimensões como um problema com apenas 20 itens, haveria um número enorme de respostas. Em um problema com mais de 80 itens, o algoritmo levaria biliõesbilhões de anos para ser concluído. Assim, o método de resolução por enumeração exaustiva é de utilidade muito reduzida, senão mesmo nula, para problemas de grande dimensão.

No Método Guloso, uma solução ótima é definida por uma sequência de decisões ótimas locais. Quando esse método não funciona, uma possível saída seria gerar todas as possíveis sequências de decisões e escolher a melhor sequência, como no ''Backtracking''. Porém essa solução é ineficiente, por ser de ordem exponencial. Na programação dinâmica é possível avaliar todas as soluções, garantido assim que a resposta final estará correta, e armazenar resultados anteriores impedindo dessa forma contas repetidas, o que deixa esse algoritmo mais eficiente.