DP de Mochila Ilimitada e Troco de Moedas
Use os itens qualquer número de vezes.
DP de Mochila Ilimitada e Troco de Moedas é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Itens ilimitados
Na mochila ilimitada, cada item pode ser escolhido quantas vezes você quiser. Pense em moedas de uma máquina de vendas, não em uma pilha fixa.
A pequena mudança
Em comparação com 0/1, apenas a direção do laço muda. Para itens ilimitados, percorra a capacidade para a frente, do menor valor para o maior.
A reutilização para a frente é o objetivo
Ao avançar, dp[w - coin] talvez já inclua este mesmo item. Essa reutilização intencional é exatamente o que permite escolhê-lo novamente.
Conheça o problema do troco
O clássico problema do troco pede o menor número de moedas cuja soma seja igual a um valor. É uma DP ilimitada com mínimo em vez de máximo.
Defina o estado
Seja dp[a] o menor número de moedas necessário para formar o valor a. Comece definindo dp[0] = 0, pois zero não precisa de moedas.
dp = [float("inf")] * (amount + 1)
dp[0] = 0Use infinito para o impossível
Valores inalcançáveis começam como infinito. Se um valor continuar infinito ao final, nenhuma combinação de moedas poderá formá-lo.
A transição
Para cada moeda, tente melhorar todos os valores que ela pode alcançar. Use uma moeda a mais que o menor valor restante.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)Por que a ordem para a frente
Percorrer os valores em ordem crescente permite que dp[a - coin] já conte esta moeda. É assim que uma única moeda contribui várias vezes.
Conte maneiras em vez disso
Troque min+1 por uma soma para contar o número de maneiras de formar cada valor. Manter o laço das moedas por fora evita contar as ordens duas vezes.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]Leia o resultado
Sua resposta está em dp[amount]. Na versão do mínimo, um valor infinito significa que o alvo é impossível de formar.
0/1 versus ilimitada
Lembre-se da única troca: a capacidade para trás significa usar cada item uma vez; para a frente significa uso ilimitado. A mesma tabela, com varredura oposta.
Verificação rápida
Teste o que torna a mochila ilimitada.
Recapitulação
Você inverteu o laço para a frente para permitir a reutilização ilimitada e construiu o problema do troco usando mínimo para obter o menor número de moedas ou soma para contar o total de maneiras. 💰
Perguntas Frequentes
A aula “DP de Mochila Ilimitada e Troco de Moedas” é grátis?
Sim — o texto completo de “DP de Mochila Ilimitada e Troco de Moedas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “DP de Mochila Ilimitada e Troco de Moedas”?
Use os itens qualquer número de vezes. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “DP de Mochila Ilimitada e Troco de Moedas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Mochila 0/1: Escolher ou Deixar
- Mochila com Espaço Otimizado
- DP de Mochila Ilimitada e Troco de Moedas
- Soma de Subconjuntos e Particionamento