Mochila com Espaço Otimizado
Reduza duas dimensões a uma única linha.
Mochila com Espaço Otimizado é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 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 Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Por que otimizar o espaço
Uma tabela completa consome n vezes cap de memória, o que pode explodir com entradas grandes. A otimização de espaço reduz isso a uma única linha reutilizada.
Apenas a última linha importa
Observe que cada célula lê apenas a linha anterior, nunca algo mais antigo. Portanto, você não precisa armazenar toda a grade de uma vez.
Reduza a um vetor
Mantenha um vetor dp de comprimento cap+1. Ao processar cada item, atualize-o no próprio lugar para representar a nova linha.
dp = [0] * (cap + 1)A armadilha da reutilização
Se você percorrer a capacidade da esquerda para a direita, dp[w - wt[i]] talvez já tenha sido atualizado para este mesmo item. Isso permitiria pegar o item i duas vezes.
Percorra a capacidade para trás
A solução é percorrer a capacidade do maior valor para o menor. Ir para trás garante que dp[w - wt[i]] ainda contenha o valor do item anterior.
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Por que percorrer para trás funciona
Ao calcular dp[w], o índice menor w - wt[i] ainda não foi alterado nesta rodada, portanto reflete a linha anterior como desejado.
Pare no peso do item
Capacidades menores que wt[i] não comportam o item, então o laço para em wt[i]. Ignorá-las economiza algumas iterações inofensivas.
O laço completo
A solução inteira consiste em dois laços aninhados sobre um vetor. Itens por fora, capacidade para trás por dentro, e a resposta surge.
for i in range(n):
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Leia a célula final
Depois de todos os itens, dp[cap] contém o valor máximo. É o mesmo número que a tabela 2D forneceria, usando muito menos memória.
Mesmo tempo, menos memória
Você não acelerou o algoritmo; ele ainda executa trabalho da ordem de n vezes cap. Você apenas reduziu a memória de quadrática para linear.
Quando vale a pena
Esse truque ajuda quando cap é grande e a grade 2D ultrapassaria o limite de memória. É um clássico das competições que vale a pena memorizar.
Verificação rápida
Teste a regra principal da mochila 1D.
Recapitulação
Você reduziu a tabela 2D a um vetor e percorreu a capacidade para trás para manter a correção, trocando memória quadrática por linear. 🚀
Perguntas Frequentes
A aula “Mochila com Espaço Otimizado” é grátis?
Sim — o texto completo de “Mochila com Espaço Otimizado” é 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 Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Mochila com Espaço Otimizado”?
Reduza duas dimensões a uma única linha. Você pratica Coding Interview Prep 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 Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep 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 2 de 4.
Quanto tempo leva a aula “Mochila com Espaço Otimizado”?
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 Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep 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