Problema da mochila: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 73:
Programação Dinâmica, ou Função Recursiva, foi a primeira técnica mais inteligente que foi usada para resolver esse problema, na década de 50. É um método aprimorado de usar recursividade que ao invés de chamar uma função várias vezes ele, na primeira vez que é chamado, armazena o resultado para que cada vez que a função for chamada novamente volte o resultado e não uma requisição para ser resolvida.
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.
==== Ilimitado ====
| |||