Troco exato com moedas ilimitadas
A missão
Problema
Uma máquina de venda tem um estoque ilimitado de moedas de cada valor listado em coins. Retorne True se ela consegue devolver exatamente amount; caso contrário, False.
Exemplos
Input: coins = [4, 7], amount = 15
Output: True
Por quê: 4 + 4 + 7 = 15
Input: coins = [4, 6], amount = 9
Output: False
Por quê: toda combinação de 4 e 6 dá um número par
Input: coins = [5], amount = 0
Output: True
Por quê: edge case: pagar zero não precisa de nenhuma moeda
Dicas
0 / 3
Sempre pegar a maior moeda falha: com moedas de 4 e 7, pegar o 7 primeiro para 16 deixa 9, que nenhuma combinação de 4 e 7 consegue pagar, embora 4 + 4 + 4 + 4 funcione. Pense em quais valores dá para pagar.
Um valor a pode ser pago se, para alguma moeda, o valor a menos essa moeda pode ser pago. O valor 0 é pago sem nenhuma moeda.
Mantenha uma lista de booleanos indexada pelo valor, com o índice 0 marcado como True. Para cada moeda, percorra os valores para cima a partir do valor da moeda e marque a como pagável quando a menos a moeda for. Percorrer para cima permite usar a mesma moeda de novo.
- Tempo-alvo
- O(len(coins) · amount)
- Espaço-alvo
- O(amount)
Restrições
- unlimited supply of every coin
Solução
Este é o problema da mochila ilimitada com resposta de sim ou não, a metade de viabilidade do Coin Change (problema do troco). ok[a] diz se o valor a pode ser pago, e uma moeda torna a pagável quando a - coin já era. O loop sobre os valores vai para cima, então, quando chega em a, a entrada de a - coin pode já incluir essa mesma moeda, que é exatamente o que um estoque ilimitado permite. Percorrer para baixo transformaria isso no problema de usar cada moeda uma única vez. O tempo é O(len(coins) · amount) e o espaço é O(amount).
def can_pay(coins, amount):
ok = [False] * (amount + 1)
ok[0] = True # zero needs no coins
for coin in coins:
for a in range(coin, amount + 1): # upward: a coin may be reused
if ok[a - coin]:
ok[a] = True
return ok[amount]
print(can_pay([4, 7], 15)) # -> True
print(can_pay([4, 6], 9)) # -> False
print(can_pay([5], 0)) # -> TrueTravou na ideia, e não no código? Coin Change explica isso.