#79 Exercício - Pedido de Desculpas

Nome: Pedido de Desculpas
Link: http://br.spoj.pl/problems/DESCULPA/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.24
Memória usada: 2.8M
Colocação alcançada: 100+
Tentativas: 3

Comentário:
Demorei um pouco, mas consegui.
Pra quem não conhece esse exercício trata de um problema famoso da área, o problema da mochila (knapsack problem).
Esse problema é um NP-Completo, portanto não há um método "perfeito" de resolvê-lo.
Entre as soluções estudadas até então estão a força bruta, a programação dinâmica e um método guloso.
A força bruta estourou o tempo quando eu tentei. Então estudei a programação dinâmica e deu certo.
O método guloso eu não cheguei a testar, mas fica a dica pra quem quiser.

Dicas:
- Estudem o problema da mochila (knapsack problem). Recomendo o método por programação dinâmica.