Identifique Quando a Estratégia Gulosa Falha
Encontre contraexemplos antes de confiar nela.
Identifique Quando a Estratégia Gulosa Falha é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 4 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 estratégia gulosa é tentadora
A estratégia gulosa é curta, rápida e parece óbvia, exatamente por isso ela pode prendê-lo em uma armadilha. Uma ideia simples não é necessariamente correta. ⚠️
A armadilha do troco
Com moedas de 1, 3 e 4, para formar 6, a estratégia gulosa escolhe 4 e depois precisa de duas moedas de 1, totalizando três moedas. A melhor solução é usar duas moedas de 3.
O que deu errado
A maior moeda foi uma vitória local que bloqueou a melhor solução global. A estratégia gulosa não conseguiu desfazer essa escolha e perdeu a resposta com duas moedas.
Encontre um contraexemplo
A verificação mais rápida é um pequeno contraexemplo: uma entrada pequena em que a estratégia gulosa e o verdadeiro ótimo sejam diferentes. Um único contraexemplo basta para rejeitá-la.
A mochila 0/1 novamente
A estratégia gulosa pela proporção falha para itens indivisíveis: um item pequeno e denso pode impedir a escolha de dois itens que, juntos, superam o valor dele. Dividir os itens era a liberdade que faltava.
Quando as escolhas interagem
Se escolher um item mudar quais outros ainda valem a pena, a estratégia gulosa frequentemente falha. Dependências complexas indicam que você deve recorrer a DP.
Faça um teste de estresse
Escreva uma solução lenta de força bruta e um gerador aleatório, depois compare ambas em milhares de casos pequenos. Uma única divergência revela a falha.
for _ in range(10000):
t = random_case()
assert greedy(t) == brute(t)O teste da troca
Para confiar na estratégia gulosa, tente provar um argumento de troca. Se você não conseguir mostrar que a escolha gulosa faz parte de alguma solução ótima, continue desconfiando.
A estratégia gulosa como sub-rotina
Mesmo quando ela não é a resposta completa, a estratégia gulosa pode ser um bloco de construção dentro de uma DP ou busca maior. Use-a onde ela for comprovadamente segura.
Leia as restrições
Um N pequeno geralmente significa que você nem precisa de uma estratégia gulosa. A força bruta ou a DP podem passar, evitando completamente o risco de incorreção.
Um hábito que ajuda a ganhar pontos
Antes de enviar uma aposta gulosa, passe um minuto procurando um contraexemplo. Essa pequena verificação evita um doloroso resultado de resposta errada.
Verificação rápida
Você suspeita que uma estratégia gulosa possa estar errada.
Recapitulação
A estratégia gulosa falha quando uma vitória local bloqueia a melhor solução global, como acontece com alguns conjuntos de moedas e com a mochila 0/1. Procure contraexemplos e faça testes de estresse antes de confiar nela. 🚀
Perguntas Frequentes
A aula “Identifique Quando a Estratégia Gulosa Falha” é grátis?
Sim — o texto completo de “Identifique Quando a Estratégia Gulosa Falha” é 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 “Identifique Quando a Estratégia Gulosa Falha”?
Encontre contraexemplos antes de confiar nela. 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 4 de 4.
Quanto tempo leva a aula “Identifique Quando a Estratégia Gulosa Falha”?
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
- A Mentalidade Gulosa
- Seleção de Atividades pelo Término Mais Cedo
- Mochila Fracionária por Proporção
- Identifique Quando a Estratégia Gulosa Falha