Roteiro 4

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

< Voltar para: Roteiros | Roteiro 3

Introdução

Neste roteiro, estudaremos problemas com soluções gulosas ou por meio de programação dinâmica. Programação dinâmica é um dos paradigmas mais importantes para solução de problemas. Saber distinguir problemas que demandam uma solução por programação dinâmica de problemas para os quais existem soluções gulosas é uma habilidade muito importante, uma vez que, geralmente, as soluções gulosas são mais simples e muito eficientes, o que faz com que soluções por programação dinâmica não sejam aceitas. Entretanto, nem sempre é óbvio que uma solução gulosa é correta. Na maioria das vezes, algoritmos gulosos são apenas métodos aproximados, que não têm valor na Maratona de Programação, e uma solução por programação dinâmica é o meio de se obter a resposta exata.

Os problemas desse roteiro foram escolhidos com o objetivo de apresentar problemas com soluções gulosas e de programação dinâmica, além de exercitar a diferença entre os dois paradigmas.

Materiais de apoio

Problemas

Lista de problemas para serem resolvidos. A solução está disponível, mas recomendamos que não a consulte antes de muito esforço. Lembre-se de resolver os problemas de aquecimento primeiro (rosa), para já ir se acostumando com o nível dos problemas.

Roteiro 4
# Problema Link Online Judge Nível Observações
1 MARAT09 Maratona SPOJ-BR 1 Aquecimento
2 BIT Bits Trocados SPOJ-BR 2 greedy coin change
3 MOEDAS Moedas SPOJ-BR 2 coin change
4 DESCULPA Pedido de Desculpas SPOJ-BR 2 0-1 knapsack
5 JDENTIST Dentista SPOJ-BR 2 greedy schedule
6 BAPOSTAS O Bolo de Apostas SPOJ-BR 2 subsequência contígua de soma máxima
7 TESOURO Caça ao Tesouro SPOJ-BR 2 subset sum
8 UVa 231 Testing the CATCHER UVa 2 longest increasing subsequence
9 UVa 10465 Homer Simpson UVa 2 -
10 UVa 10152 ShellSort UVa 2 -
11 SAMER08C Candy SPOJ 1 -
12 IOIPALIN Palindrome 2000 SPOJ 2 Longest common subsequence
13 ACODE Candy SPOJ-BR 2 -
14 MCOINS Coins Game SPOJ 2 -
15 Knapsack The Knapsack problem SPOJ 1 0-1 Knapsack
16 MCIRGAME Point Connection Game in a Circle SPOJ 2 -
17 UVa 11450 Wedding shopping UVa 2 -
18 UVa 10943 How do you add? UVa 2 -
19 UVa 108 Maximum sum UVa 2 Maximum Sum 2d Matrix
20 ICPC6762 Omar Loves Candies ACM-ICPC Live Archive 1 -
21 CORMENMG O Código de Cormen SPOJ-BR 3 Greedy Schedule & Busca Binaria .

Próximo roteiro

O próximo roteiro de treinamento tratará de problemas com algoritmos básicos em grafos. Recomendamos que você avance apenas depois de ler todo o material de apoio e ter feito todos os problemas.

Link para o Roteiro 5

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas