Vales-presente para um total exato
A missão
Problema
Você tem vales-presente com os valores em cards, e cada vale pode ser usado no máximo uma vez. Um vale precisa ser usado por inteiro. Retorne True se alguns dos vales somarem exatamente total; caso contrário, False.
Exemplos
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ê: os vales pequenos somam só 26, e o vale de 34 sozinho já é demais
Input: cards = [7], total = 0
Output: True
Por quê: edge case: não usar nenhum vale paga exatamente zero
Dicas
0 / 3
Testar todos os subconjuntos de vales custa 2 elevado a n. A única coisa que importa em um grupo de vales é o total que ele alcança.
Acompanhe quais totais, de 0 até o alvo, podem ser alcançados com os vales vistos até agora. Adicionar um vale torna um total t alcançável se t menos esse vale já era alcançável antes dele.
Mantenha uma lista de booleanos indexada pelo total, com o índice 0 marcado como True. Para cada vale, percorra os totais do alvo até o valor do vale, de cima para baixo, e marque t como alcançável quando t menos o vale for. Percorrer de cima para baixo impede que um vale seja usado duas vezes.
- Tempo-alvo
- O(n · total)
- Espaço-alvo
- O(total)
Restrições
- each card is used at most once and in full
Solução
Este é o problema da mochila 0/1 (0/1 knapsack) com resposta de sim ou não, muitas vezes chamado de soma de subconjuntos (subset sum). reachable[t] diz se alguns dos vales vistos até agora somam exatamente t, e cada novo vale ou fica de fora, deixando a entrada como estava, ou entra, copiando a resposta de reachable[t - card]. O loop interno vai dos totais altos para os baixos, para que reachable[t - card] ainda descreva os vales anteriores a este, e é isso que limita cada vale a um único uso. O tempo é O(n · total) e o espaço é 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)) # -> TrueTravou na ideia, e não no código? Mochila 0/1 explica isso.