Programação dinâmica

Em programação dinâmica os problemas são divididos em etapas.

Cada etapa está associada a vários estados que correspondem a várias soluções admissíveis

A decisão tomada em cada etapa transforma o estado da etapa corrente para ser o estado inicial da próxima etapa.

A cada etapa a decisão tomada irá manter o plano ótimo de decisões e fornece igualmente  o ponto ótimo a cada estado.

As decisões numa etapa são independente das decisões anteriores.

As equações recursivas fazem depender o máximo de uma etapa dos valores obridos em etapas anteriores.

 

Knapsack

Nestes problemas consideram-se n objectos em vez de n etapas, indo-se seleccionando os objectos.

Leave a Reply

Your email address will not be published. Required fields are marked *