Como seguimento do artigo de introdução a algoritmos greedy, apresentamos aqui alguns problemas clássicos que admitem uma solução greedy. Estes diferentes problemas mostram como diferentes ideias greedy podem ser aplicadas e por isso cada um ensina algo de novo.

Lista de problemas

Os problemas clássicos que iremos estudar são os seguintes:

  • Problema do troco/moeda;
  • Seleção de intervalos;
  • Minimização de somas;
  • Códigos de Huffman;

Para aprenderem a teoria de cada um, consultem o seguinte artigo bastante completo:

Artigo: Exemplos de problemas greedy

Capítulo 6 do livro "Competitive Programmer’s Handbook", páginas 57 a 64

Nota: Competitive Programmer’s Handbook

O livro está disponível no link seguinte: https://cses.fi/book.pdf

Existem mais problemas clássicos com soluções greedy que podem opcionalmente investigar, como o problema da mochila fracionária (em inglês, fractional knapsack). Se quiserem uma fonte extra de informação, consultem o artigo seguinte:

*Artigo: Artigo sobre algoritmos greedy

Artigo do TopCoder sobre algoritmos greedy

Aplicações

Se quiserem praticar alguns problemas baseados nos exemplos que viram aqui têm uma sugestão:

Problema 1: Entertainment Box

Problema do Kattis, entertainmentbox - Entertainment Box

Opcionalmente, aqui têm mais um problema, um pouco mais complicado:

*Problema 2: Canvas Painting

Problema C da prova SWERC16 do codeforces - Canvas Painting