Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dynamic Programming, Approximation Algorithms for NP-Hard Problems -…
Dynamic Programming
Knapsack problem
Dados n itens de pesos conhecidos w1, ..., wn e valores v1, ..., vn e uma mochila de capacidade W, encontre o subconjunto mais valioso dos itens que cabem na mochila.
Construir um array de tamanho n X K +1 que contém todas as soluções para todos os subproblemas P(i,k)
Começar o problema de tamanho P(n,k) e fazer chamadas recursivas resolvendo os subproblemas. Checa se já foi resolvido e guarda os valores encontrados
Começar preenchendo o array pra fila 1. Depois, preenche as próximas filas de 2 a n (esquerda pra direita)
A eficiência de tempo e eficiência de espaço deste algoritmo são ambas em Theta (nW). O tempo necessário para encontrar a composição de uma solução ótima está em O (n).
3 exemplos
Coin-row problem
Há uma linha de n moedas cujos valores são alguns inteiros positivos c1, c2, ..., cn, não necessariamente distintos. O objetivo é coletar a quantidade máxima de dinheiro sujeito à restrição de que duas moedas adjacentes na linha inicial não possam ser coletadas
Change-making problem
Considere a instância geral do seguinte problema conhecido. Dê o troco para o valor n usando o número mínimo de moedas de denominações d1 <d2 <... <dm. Para as denominações das moedas usadas nos Estados Unidos, como para aquelas usadas na maioria, senão em todos os outros países, existe um algoritmo muito simples e eficiente discutido no próximo capítulo. Aqui, consideramos um algoritmo de programação dinâmica para o caso geral, assumindo a disponibilidade de quantidades ilimitadas de moedas para cada uma das m denominações d1 <d2 <... <dm onde d1 = 1.
Coin-collecting problem
Várias moedas são colocadas em células de um tabuleiro n × m, não mais do que uma moeda por célula. Um robô, localizado na célula superior esquerda do tabuleiro, precisa coletar o máximo de moedas possível e trazê-las para a célula inferior direita. Em cada etapa, o robô pode mover uma célula para a direita ou uma célula para baixo de sua localização atual. Quando o robô visita uma célula com uma moeda, ele sempre pega a moeda.
A programação dinâmica é uma técnica para resolver problemas com subproblemas sobrepostos. Normalmente, esses subproblemas surgem de uma recorrência relacionando 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.
-