Algoritmos e Programação de Computadores II
Prof. MSc. Leanderson André
leandersonandre@univille.br
Universidade da Região de Joinville
Dado um conjunto de moedas = {c1,c2,…ck} e uma quantidade dinheiro alvo n, encontre a menor combinação de moedas que somados resulta na quantidade n.

Exemplo: moedas = {1,2,5}, alvo = 12.
Qual é a solução ótima?
3 moedas
5 + 5 + 2 = 12
Exemplo: moedas = {1,2,5}, alvo = 12.
Qual foi a estratégia adotada?
Selecione sempre a maior moeda sem exceder o valor da soma.
Algoritmo guloso
Exemplo: moedas = {1,3, 4}, alvo = 6.
Qual é a solução ótima?
Algoritmo guloso: 3 moedas: 4 + 1 + 1 = 6
Solução ótima: 2 moedas: 3 + 3 = 6
Algoritmos gulosos não garantem a solução ótima.
Algoritmos de força bruta garantem a solução ótima por explorar todas as possibilidades, mas podem ser muito lentos para uma grande quantidade de dados de entrada.
A programação dinâmica pode encontrar a solução ótima como a força bruta mas sendo eficiente.
O problema pode ser reformulado de maneira recursiva para encontrar a solução para os seus subproblemas.
Por exemplo: moedas = {1,3,4}
| Expressão | Valor | Expressão | Valor |
|---|---|---|---|
resolver(0) |
0 | resolver(6) |
2 |
resolver(1) |
1 | resolver(7) |
2 |
resolver(2) |
2 | resolver(8) |
2 |
resolver(3) |
1 | resolver(9) |
3 |
resolver(4) |
1 | resolver(10) |
3 |
resolver(5) |
2 |
A propriedade essencial de resolver é que seus valores podem ser calculadas recursivamente para os valores menores.
Por exemplo: moedas = {1,3,4}
resolver(x) = min(resolver(x-1) + 1,
resolver(x-3) + 1,
resolver(x-4) + 1)
O caso base da recursão é resolver(0) = 0.
A cada nível, uma moeda é utilizada.
Caminhos das soluções possíveis.
Por exemplo: moedas = {1,3,4}, soma = 10
resolver(10) = resolver(7) + 1 // x - 3
= resolver(4) + 2 // x - 2
= resolver(0) + 3 // x - 4
= 3 $$ \operatorname{resolver}(x)= \begin{cases} \infty, & x < 0 \\ 0, & x = 0 \\ \displaystyle\min_{c \in \text{moedas}} \left\{\operatorname{resolver}(x-c)+1\right\}, & x > 0 \end{cases}$$
Codifique a solução recursiva para o problema do troco utilizando a linguagem Python.
Entrada: moedas = {1,3,4}, x = 10
Saída: 3
def resolver(soma,moedas):
if soma < 0:
return float('inf')
if soma == 0:
return 0
menor = float('inf')
for m in moedas:
r = resolver(soma-m, moedas) + 1
menor = min(menor,r)
return menormoedas = [1,3,4]
resultado = resolver(10,moedas)
print("Resultado:",resultado)A idéia chave na programação dinâmica é a memoização.
Deve-se verificar se a tabela já contêm a solução para aquela instância do problema.
Caso tiver, utilize a solução armazenada.
if soma in tabela:
return tabela[soma]Caso contrário, calcule a solução. Após identificar a melhor solução para a determinada instância do problema, armazene a solução na tabela.
def resolver(soma,moedas,tabela={}):
if soma < 0:
return float('inf')
if soma == 0:
return 0
if soma in tabela:
return tabela[soma]
menor = float('inf')
for m in moedas:
r = resolver(soma-m, moedas, tabela) + 1
menor = min(menor,r)
tabela[soma] = menor
return menorImplementação iterativa pode apresentar algumas vantagens como possuir uma implementação mais simples e uso constante de memória.
def resolver(soma,moedas):
tabela={0:0}
for i in range(1,soma+1):
tabela[i] = float('inf')
for m in moedas:
if i-m >= 0:
tabela[i] = min(tabela[i],tabela[i-m]+1)
return tabela[soma]Algumas vezes, um determinado problema solicita qual é sua a solução ótima. No problema do troco, é necessário uma estrutura de dados para armazenar a primeira moeda da solução que resolve o problema.
def resolver(soma,moedas):
tabela={0:0}
solucao={}
for i in range(1,soma+1):
tabela[i] = float('inf')
for m in moedas:
if i-m >= 0 and tabela[i-m]+ 1 < tabela[i]:
tabela[i] = min(tabela[i],tabela[i-m]+1)
solucao[i] = m
# Imprimir no terminal neste ponto
return tabela[soma]Para apresentar a solução ótima no terminal.
s = soma
print("Solução: ",end="")
while s > 0:
print(solucao[s],end="")
s -= solucao[s]
print()Dado o problema do troco, crie uma solução utilizando a programação dinâmica que retorne a quantidade de soluções válidas.
Entrada: moedas = {1 ,3, 4}, soma = 5
Saída: 6
| 1 + 1 + 1 + 1 + 1 | 3 + 1 + 1 |
| 1 + 1 + 3 | 1 + 4 |
| 1 + 3 +1 | 4 + 1 |
Dada uma sequência de números inteiros, encontre o tamanho da maior subsequência estritamente crescente (não necessariamente contínua). Uma subsequência é formada removendo zero ou mais elementos da sequência original, sem alterar a ordem relativa dos elementos restantes. Crie uma solução utilizando programação dinâmica para determinar o comprimento da Longest Increasing Subsequence (LIS).
Entrada: sequência = {10, 22, 9, 33, 21, 50, 41, 60}
Saída: 5
Entrada: sequência = {10, 22, 9, 33, 21, 50, 41, 60}
Saída: 5
Explicação: A maior subsequência crescente possui comprimento 5.
| 10 → 22 → 33 → 50 → 60 |
| 10 → 22 → 33 → 41 → 60 |
Prof. MSc. Leanderson André
leandersonandre@univille.br
Universidade da Região de Joinville