Mochila 0/1: Escolher ou Deixar
Maximize o valor sob um limite de peso.
Mochila 0/1: Escolher ou Deixar é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 1 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.
A história da mochila
Você tem uma mochila com um limite de peso e uma pilha de itens. A mochila 0/1 pergunta: quais itens maximizam o valor sem ultrapassar a capacidade? 🎒
Pegue ou deixe
O termo 0/1 significa que cada item é totalmente escolhido ou totalmente ignorado. Você nunca pode pegar metade de um item, portanto cada escolha é sim ou não.
Por que a estratégia gulosa falha
Pegar primeiro o item mais barato ou mais valioso pode desperdiçar capacidade. O atalho da estratégia gulosa falha aqui, então é necessário considerar combinações reais.
As duas entradas
São fornecidas duas listas paralelas: um peso e um valor para cada item, além de uma capacidade. O item i tem peso wt[i] e valor val[i].
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7Defina o estado
Seja dp[i][w] o melhor valor usando os primeiros i itens com capacidade w. Dar um nome preciso ao estado é o ponto central.
A escolha de deixar
Se você deixar o item i, seu valor será o que já tinha: dp[i-1][w]. A capacidade permanece inalterada para o restante.
A escolha de pegar
Se você pegar o item i, adicione seu valor e reduza a capacidade: val[i] + dp[i-1][w - wt[i]]. Isso só é permitido quando w é pelo menos wt[i].
Escolha o melhor ramo
A recorrência simplesmente mantém a maior das duas opções usando max. Cada célula confia nas respostas já calculadas abaixo dela.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])A linha-base
Com zero itens, você pode transportar valor zero em qualquer capacidade. Esse caso-base preenche a primeira linha com zeros, que servirão de base.
dp = [[0] * (cap + 1) for _ in range(n + 1)]Preencha a tabela
Percorra os itens no laço externo e as capacidades no laço interno. Cada célula lê apenas a linha acima, então uma única passagem preenche tudo.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]Leia a resposta
A célula inferior direita dp[n][cap] contém o valor máximo para todos os itens e toda a capacidade. Essa única célula é sua resposta final.
Verificação rápida
Teste a recorrência central da mochila 0/1.
Recapitulação
Você aprendeu a mochila 0/1: cada item é uma escolha entre pegar e deixar, dp[i][w] mantém o melhor entre deixar e pegar, e dp[n][cap] é a resposta. 🎉
Perguntas Frequentes
A aula “Mochila 0/1: Escolher ou Deixar” é grátis?
Sim — o texto completo de “Mochila 0/1: Escolher ou Deixar” é 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 “Mochila 0/1: Escolher ou Deixar”?
Maximize o valor sob um limite de peso. 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 1 de 4.
Quanto tempo leva a aula “Mochila 0/1: Escolher ou Deixar”?
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