Cambio exacto con monedas ilimitadas
La misión
Problema
Una máquina expendedora tiene una cantidad ilimitada de monedas de cada denominación listada en coins. Devuelve True si puede dar de cambio exactamente amount; si no, devuelve False.
Ejemplos
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 combinación de 4 y 6 es par
Input: coins = [5], amount = 0
Output: True
Por qué: caso límite: pagar cero no necesita monedas
Pistas
0 / 3
Tomar siempre la moneda más grande falla: con monedas de 4 y 7, tomar primero el 7 para 16 deja 9, que ninguna combinación de 4 y 7 puede pagar, aunque 4 + 4 + 4 + 4 funciona. Piensa en qué montos se pueden pagar.
Un monto a se puede pagar si, para alguna moneda, el monto a menos esa moneda se puede pagar. El monto 0 se paga sin monedas.
Mantén una lista de booleanos indexada por monto, con el índice 0 en True. Para cada moneda, recorre los montos hacia arriba desde el valor de la moneda y marca a como pagable cuando a menos la moneda lo sea. Recorrer hacia arriba permite volver a usar la misma moneda.
- Tiempo objetivo
- O(len(coins) · amount)
- Espacio objetivo
- O(amount)
Restricciones
- unlimited supply of every coin
Solución
Este es el problema de la mochila no acotada con una respuesta de sí o no: la mitad de factibilidad de Coin Change. ok[a] indica si el monto a se puede pagar, y una moneda vuelve pagable el monto a cuando a - coin ya lo era. El bucle sobre los montos va hacia arriba, así que cuando llega al monto a, la entrada de a - coin puede incluir ya esta misma moneda, que es justo lo que permite una cantidad ilimitada. Recorrerlo hacia abajo lo convertiría, en cambio, en el problema de usar cada moneda una sola vez. El tiempo es O(len(coins) · amount) y el espacio es 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)) # -> True¿Lo que te frena es la idea y no el código? Coin Change lo explica.