Algoritmos e Estruturas de Dados

Troco de Moedas

💡
O problema do troco de moedas é um dos mais populares entre os problemas de Programação Dinâmica. Ele demonstra claramente o contraste entre as abordagens Gananciosa (Greedy) e de Programação Dinâmica, e como é fácil cair na armadilha de pensar que a estratégia gananciosa pode ser suficiente, quando na verdade esse método só conduz a uma solução subótima em vez de resolver o problema de forma global.
Suponha que temos um sistema monetário composto por n moedas, em que cada moeda tem um valor positivo . O objetivo é encontrar uma forma de obter o valor total x utilizando o menor número possível de moedas.
Por exemplo, se as moedas disponíveis forem e precisarmos de obter 11, a melhor escolha seria 1 + 5 + 5 ⇒ 3 moedas.

Entrada

A primeira linha da entrada contém dois inteiros n (1 ≤ n ≤ 100) e x (1 ≤ x ≤ ).
A linha seguinte contém n inteiros separados por espaços (1 ≤ ≤ ).

Saída

O programa deve imprimir o número mínimo de moedas necessário para se obter x. Se não for possível obter a soma desejada x, deve ser impresso -1.

Exemplos

Input
Output
3 11 1 5 7
3
3 12 1 5 7
2

Explicação

  1. 11 → 1 + 5 + 5
  1. 12 → 5 + 7
 

Tutorial

Repare que a estratégia gananciosa de escolher sempre a maior moeda disponível não é suficiente. O primeiro exemplo deixa isso bem claro: se quisermos obter 11 começando pela maior moeda (7), ficamos a precisar de 4, o que nos obrigaria a usar quatro moedas de 1, perfazendo 5 moedas no total. Contudo, a resposta ótima usa apenas 3 moedas (5 + 5 + 1).
Definimos então um estado d[i] para representar o menor número de moedas necessário para obter a soma i. Se conseguirmos inicializar d de forma adequada e depois atualizar todos os valores até x, a resposta final será d[x].
De início, podemos definir todos os valores de d como infinito (significando que ainda não é possível obter esse total) e, para 0, atribuir 0 moedas:
c = [...]
x = ...
d = [0] + [float('inf')] * x      # d[0] é 0 e d[1...x] é infinito
Depois, para cada número 1...x, tentamos descobrir o menor número de moedas possível. Assim que determinamos um valor para num, testamos todas as moedas para ver se conseguimos obter num somando o valor dessa moeda a algum estado anterior (num - $$c_i$$). Se isso produzir um resultado melhor, atualizamos d[num]. Portanto, para cada num em 1...x, analisamos todos os estados anteriores úteis e tentamos melhorar d[num]:
for num in range(1, x + 1):       # Iterar sobre todos os números de 1 a x
    for ci in c:                  # Tentar melhorar d[num] com todas as moedas
        if num - ci >= 0:         # Se for possível conseguir num com esta moeda
            d[num] = min(d[num], d[num - ci] + 1)
print(d[x])
A expressão d[num] = min(d[num], d[num - ci] + 1) é essencial para a solução do problema. A cada iteração, tentamos melhorar o valor de d[num] caso haja como fazê-lo através de num - $$c_i$$. Ou seja, pegamos o número mínimo de moedas que obtém num - $$c_i$$ e adicionamos 1 à contagem ao usar a moeda .
Ao final do processo, depois de termos percorrido todos os valores para todas as moedas, teremos a resposta em d[x].
Para visualizar o algoritmo em ação, vejamos como ele funciona no exemplo:
c = [1, 5, 7] e x = 11
  1. d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
  1. num = 1 (tentar melhorar o número de moedas para obter a soma 1) ci = 1 ⇒ d[1] = d[0] + 1 = 1 ⇒ d = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 2 (tentar melhorar o número de moedas para obter a soma 2) ci = 1 ⇒ d[2] = d[1] + 1 = 2 ⇒ d = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 3 (tentar melhorar o número de moedas para obter a soma 3) ci = 1 ⇒ d[3] = d[2] + 1 = 3 ⇒ d = [0, 1, 2, 3, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 4 (tentar melhorar o número de moedas para obter a soma 4) ci = 1 ⇒ d[4] = d[3] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 5 (tentar melhorar o número de moedas para obter a soma 5) ci = 1 ⇒ d[5] = d[4] + 1 = 5 ⇒ d = [0, 1, 2, 3, 4, 5, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ d[5] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, ∞, ∞, ∞, ∞, ∞, ∞] ci = 7 ⇒ num - ci < 0
  1. num = 6 (tentar melhorar o número de moedas para obter a soma 6) ci = 1 ⇒ d[6] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ não atualiza ci = 7 ⇒ num - ci < 0
  1. num = 7 (tentar melhorar o número de moedas para obter a soma 7) ci = 1 ⇒ d[7] = d[6] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 3, ∞, ∞, ∞, ∞] ci = 5 ⇒ não atualiza ci = 7 ⇒ d[7] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, ∞, ∞, ∞, ∞]
  1. num = 8 (tentar melhorar o número de moedas para obter a soma 8) ci = 1 ⇒ d[8] = d[7] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, ∞, ∞, ∞] ci = 5 ⇒ não atualiza ci = 7 ⇒ não atualiza
  1. num = 9 (tentar melhorar o número de moedas para obter a soma 9) ci = 1 ⇒ d[9] = d[8] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, ∞, ∞] ci = 5 ⇒ não atualiza ci = 7 ⇒ não atualiza
  1. num = 10 (tentar melhorar o número de moedas para obter a soma 10) ci = 1 ⇒ d[10] = d[9] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, ∞] ci = 5 ⇒ d[10] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, ∞] ci = 7 ⇒ não atualiza
  1. num = 11 (tentar melhorar o número de moedas para obter a soma 11) ci = 1 ⇒ d[11] = d[10] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, 3] ci = 5 ⇒ não atualiza ci = 7 ⇒ não atualiza
  1. print(d[11]) ⇒ imprime 3
 

Constraints

Time limit: 2.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue