Material complementar

Difícil de estudar, pois os problemas podem ser muito diferentes entre si

• Tentar ver alguns problemas clássicos para entender algumas "sacadas" mais famosas
• Normalmente, pensa alguma ideia e tenta se convencer "por que isso não dá certo?"
  • Contra-exemplos ou provas por indução (em casos mais extremos)

Problemas famosos

• Minimizar a quantidade de pulos de um sapo para atravessar a poça sem cair na água
• Maximizar o número de eventos em que se pode ir (sem intersecção)
• Minimizar o custo das arestas para escolher de forma que o grafo continue conexo (MST)
• Minimizar a quantidade de moedas para formar um valor (problema do troco)

Abordagens citadas

Para tentar "formalizar" um pouco a abordagem de se pensar se algoritmo guloso funciona, existem essas técnicas (citadas nos artigos complementares acima):

• "Greedy stays ahead": tentar provar que a solução gulosa é sempre melhor ou igual a qualquer outra solução possível.
• Exchange arguments: pense em outra possível solução, e tente transformá-la em uma solução gerada pelo algoritmo guloso (reordenando os elementos ou algo do tipo)

Porém, na maioria das vezes, utiliza-se a seguinte prova (não recomendada):

• Prova por AC: faz o código e tenta submeter - se passar o problema (accepted) é por que muito provavelmente está certo (ou talvez os casos de teste estão fracos - mas passou 🤪)

Exercícios auxiliares