Tarjetas de regalo para un total exacto
La misión
Problema
Tienes tarjetas de regalo con los valores de cards, y cada tarjeta se puede usar como máximo una vez. Una tarjeta debe usarse completa. Devuelve True si algunas de las tarjetas suman exactamente total; si no, devuelve False.
Ejemplos
Input: cards = [3, 34, 4, 12, 5, 2], total = 9
Output: True
Por qué: 4 + 5 = 9
Input: cards = [3, 34, 4, 12, 5, 2], total = 30
Output: False
Por qué: las tarjetas pequeñas solo suman 26, y la tarjeta de 34 sola ya se pasa
Input: cards = [7], total = 0
Output: True
Por qué: caso límite: no usar ninguna tarjeta paga exactamente cero
Pistas
0 / 3
Probar todos los subconjuntos de tarjetas cuesta 2 elevado a n. Lo único que importa de un grupo de tarjetas es el total que alcanza.
Lleva la cuenta de qué totales, desde 0 hasta el objetivo, se pueden alcanzar con las tarjetas vistas hasta ahora. Agregar una tarjeta hace alcanzable un total t si t menos esa tarjeta ya era alcanzable antes de ella.
Mantén una lista de booleanos indexada por total, con el índice 0 en True. Para cada tarjeta, recorre los totales desde el objetivo hacia abajo hasta el valor de la tarjeta y marca t como alcanzable cuando t menos la tarjeta lo sea. Recorrer hacia abajo evita que una tarjeta se use dos veces.
- Tiempo objetivo
- O(n · total)
- Espacio objetivo
- O(total)
Restricciones
- each card is used at most once and in full
Solución
Este es el problema de la mochila 0/1 (0/1 knapsack) con una respuesta de sí o no, que a menudo se llama subset sum. reachable[t] indica si algunas de las tarjetas vistas hasta ahora suman exactamente t, y cada tarjeta nueva o se queda fuera, lo que deja la entrada como estaba, o entra, copiando la respuesta de reachable[t - card]. El bucle interno va de los totales altos a los bajos para que reachable[t - card] siga describiendo las tarjetas anteriores a esta, que es lo que limita cada tarjeta a un solo uso. El tiempo es O(n · total) y el espacio es O(total).
def exact_total(cards, total):
reachable = [False] * (total + 1)
reachable[0] = True # zero is paid with no cards
for card in cards:
for t in range(total, card - 1, -1): # downward: each card used at most once
if reachable[t - card]:
reachable[t] = True
return reachable[total]
print(exact_total([3, 34, 4, 12, 5, 2], 9)) # -> True
print(exact_total([3, 34, 4, 12, 5, 2], 30)) # -> False
print(exact_total([7], 0)) # -> True¿Lo que te frena es la idea y no el código? Mochila 0/1 lo explica.