Please enable JavaScript.
Coggle requires JavaScript to display documents.
M16 - Coggle Diagram
M16
Programação Dinâmica
A programação dinâmica é uma técnica para resolver problemas com subproblemas sobrepostos. Normalmente, esses subproblemas surgem de uma recorrência que relaciona a solução de um determinado problema às soluções de seus subproblemas menores. Em vez de resolver subproblemas sobrepostos repetidamente, a programação dinâmica sugere resolver cada um dos subproblemas menores apenas uma vez e registrar os resultados em uma tabela a partir da qual uma solução para o problema original pode então ser obtida.
Uma vez que a maioria dos aplicativos de programação dinâmica lida com problemas de otimização, também precisamos mencionar um princípio geral que sublinha tais aplicativos. Richard Bellman chamou isso de princípio da otimização. Em termos um tanto diferentes de sua formulação original, ele diz que uma solução ótima para qualquer instância de um problema de otimização é composta de soluções ótimas para suas subinstâncias. O princípio da otimização é válido com muito mais frequência do que não. Embora sua aplicabilidade a um problema específico precise ser verificada, é claro, essa verificação geralmente não é a principal dificuldade no desenvolvimento de um algoritmo de programação dinâmico.
No exemplo da aplicação disso a Fibonacci, armazenam-se os valores já encontrados em um array, fazendo com que esses valores não sejam calculados mais de uma vez. Além disso, ao invés de se calcular de n até 1 e 0, faz-se o processo inverso e dessa forma só se necessita ter armazenados os dois valores anteriores.
Problema Knapsack
Dados n itens de pesos conhecidos w1,. . . , wn e os valores v1,. . . , vn e um knapsack de capacidade W, encontre o subconjunto mais valioso dos itens que cabem no knapsack.
A eficiência de tempo e eficiência de espaço deste algoritmo são ambas em Θ (nW). O tempo necessário para encontrar a composição de uma solução ótima está em Ο (n).
Constrói-se um array de tamanho n X K +1 que contém todas as soluções para todos os subproblemas P(i,k)
Começa-se o problema de tamanho P(n,k) e faz-se chamadas recursivas resolvendo os subproblemas. Checa-se se já foi resolvido e guarda os valores encontrados
Começa-se preenchendo o array para a fila 1. Na sequência, preenche-se as próximas filas de 2 a n - da esquerda para a direita
-