Desenvolvimento de Algoritmos Dinâmicos

6.1 Passos principais no desenvolvimento de algoritmos dinâmicos.

Passos principais no desenvolvimento de algoritmos dinâmicos

1. Definição das sub-tarefas:

Quebre o problema em sub-tarefas menores que podem ser resolvidas independentemente. Essas sub-tarefas devem ser sobrepostas para que os resultados de cálculos anteriores possam ser usados.

2. Identificação dos estados:

Defina todos os possíveis estados que podem ocorrer ao resolver o problema. Os estados devem descrever todas as informações necessárias para a transição de um passo para o próximo.

3. Formulação da relação de recorrência:

Defina como a solução do problema para o estado atual depende das soluções para estados anteriores. Essa relação deve expressar como obter a solução ótima, usando soluções para as sub-tarefas.

4. Definição dos casos base:

Defina os casos base, para os quais a solução do problema é conhecida diretamente sem necessidade de cálculos adicionais.

5. Preenchimento da tabela:

Crie uma tabela (geralmente um array ou matriz) para armazenar as soluções de todas as sub-tarefas. Use a relação de recorrência e os casos base para preencher a tabela de baixo para cima ou de cima para baixo.

6. Otimização (memoização):

Se uma abordagem recursiva for usada, adicione memoização para salvar os resultados das sub-tarefas e evitar cálculos repetidos.

Complexidade temporal e espacial dos algoritmos dinâmicos

Complexidade temporal:

• A complexidade temporal dos algoritmos dinâmicos é geralmente expressa pelo número de sub-tarefas e o tempo necessário para calcular cada sub-tarefa.
• Na maioria dos casos, a complexidade temporal é O(n) ou O(n^2), onde n é o tamanho dos dados de entrada.

Complexidade espacial:

• A complexidade espacial depende do número de estados que precisam ser armazenados.
• Em alguns casos, é possível reduzir a complexidade espacial com o uso de otimizações, como redução do uso de memória para O(n) ou O(1).

6.2 Problema da Mochila.

O Problema da Mochila é um problema clássico de otimização combinatória, que ocorre em várias áreas, incluindo ciência da computação, economia, e gerenciamento logístico. O principal objetivo do problema é usar de forma eficaz recursos limitados.

Descrição do Problema da Mochila

Temos uma mochila que pode aguentar um determinado peso W. Também temos n itens, cada um com um peso wt[i] e um valor val[i]. Precisamos determinar quais itens levar para maximizar o valor total dos itens na mochila, sem exceder sua capacidade de peso.

Tipos de Problema da Mochila

1. Problema da Mochila 0/1 (0/1 Knapsack Problem):

Cada item pode ser levado ou não (não pode ser dividido).

2. Problema da Mochila Fracionária (Fractional Knapsack Problem):

Cada item pode ser dividido e qualquer parte dele pode ser levada.

3. Problema da Mochila Múltipla (Multiple Knapsack Problem):

Existem várias mochilas com diferentes restrições de peso.

Formulação do problema da mochila 0/1 em termos de teoria de algoritmos:

Relação de Recorrência:

Para cada item i e para cada possível peso w (de 0 até W), a solução ótima pode ser expressa da seguinte maneira:

• Se o item i não for incluído na mochila, o valor ótimo é o valor ótimo para i − 1 itens e peso w.
• Se o item i for incluído na mochila, o valor ótimo é o valor deste item mais o valor ótimo para i − 1 itens e peso w − wt[i].

Complexidade temporal e espacial

Complexidade temporal:

A complexidade temporal deste algoritmo é O(nW) onde n é o número de itens, e W é a capacidade da mochila. Isso se deve ao fato de ser necessário preencher uma tabela de tamanho n × W.

Complexidade espacial:

A complexidade espacial também é O(nW), pois é necessária uma tabela para armazenar os resultados intermediários.

Exemplos de implementação do problema da mochila 0/1

def knapsack(W, wt, val, n):
    # Criamos uma tabela para armazenar os valores intermediários
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # Preenchemos a tabela dp de baixo para cima
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# Exemplo de uso
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"Valor máximo possível na mochila: {knapsack(W, wt, val, n)}")
        

6.3 Problema de Troco de Moedas.

O Problema de Troco de Moedas é um problema clássico de programação dinâmica, que busca encontrar o número mínimo de moedas ou o número de maneiras de alcançar um determinado valor usando um conjunto de moedas com valores definidos. Este problema tem duas variações principais:

Quantidade mínima de moedas (Minimum Coin Change Problem):

Encontrar o número mínimo de moedas que somam um determinado valor.

Número de maneiras (Number of Ways to Make Change):

Encontrar o número de diferentes maneiras de compor um determinado valor a partir de um conjunto de moedas dadas.

Variação 1. Quantidade mínima de moedas

Formulação do Problema

Dado:

• Um conjunto ilimitado de moedas com valores definidos.
• O valor alvo S.

Necessário:

• Encontrar o número mínimo de moedas que soma o valor S.

Solução usando programação dinâmica

Relação de Recorrência:

• Se dp[i] representa o número mínimo de moedas necessário para compor o valor i.
• Para cada moeda c do conjunto de moedas, se i ≥ c, então: dp[i] = min(dp[i], dp[i − c] + 1)

Casos base:

• dp[0] = 0 (para o valor 0 são necessárias 0 moedas).

Complexidade temporal e espacial:

• Complexidade temporal: O(n ⋅ S), onde n é o número de denominações de moedas, S é o valor alvo.
• Complexidade espacial: O(S), pois é necessário um array para armazenar o número mínimo de moedas para cada valor de 0 até S.

Exemplo de implementação em Python

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# Exemplo de uso
coins = [1, 2, 5]
S = 11
print(f"Quantidade mínima de moedas para o valor {S}: {min_coins(coins, S)}")
        
        

O problema de Troco de Moedas demonstra a flexibilidade da programação dinâmica. É usado para ensinar e pesquisar técnicas algorítmicas, pois mostra como usar relações de recorrência e casos base para resolver problemas de forma eficiente.