trabalho pratico cco

1. INTRODUÇÃO
Este trabalho prático tem como objetivo familiarizar com paradigmas de projetos de algoritmos, especialmente programação dinâmica e algoritmos gulosos
1.1. Definição do problema
Um guitarrista famoso vai fazer um show em Belo Horizonte. Uma das suas estratégias para fazer um show empolgante é nunca tocar duas músicas seguidas no mesmo volume. Cada vez que ele troca de música, faz alguma alteração no volume.
Para o show em BH, o guitarrista já escolheu quantas e quais músicas ele vai tocar, e também o quanto o volume deve variar (subir ou descer) de uma música para a outra. O problema agora é decidir obedecendo às variações de volume, qual o maior volume com o qual ele pode tocar a última música do espetáculo, de forma tal que em nenhum momento ultrapasse um dado volume limite.
Por
exemplo, suponha que o guitarrista vá tocar três músicas e que, da primeira para a segunda música o volume deva variar 4 unidades e da segunda para a terceira música, o volume deva variar 7 unidades. Se o volume com o qual ele vai tocar a primeira música é 5 e o volume máximo permitido é 9, há duas opções possíveis:
•Tocar a primeira música com volume 5, a segunda música com volume 5 + 4 = 9 e a terceira música com volume 9 - 7 = 2;
•Tocar a primeira música com volume 5, a segunda música com volume 5 - 4 = 1 e a terceira música com volume 1 + 7 = 8.
Dentre essas duas opções, a segunda é a que maximiza o volume com o qual a última música é tocada, e é ela que será usada.

1.2. O que será feito:
1. Será apresentada uma solução de força bruta para o problema e sua implementação;
2. Caso o problema tenha propriedade gulosa, será apresentada e implementada uma solução gulosa.
3. Caso haja sobreposição de subproblemas, será apresentada e implementada uma solução utilizando programação dinâmica.

2. SOLUÇÃO PROPOSTA
2.1. FORÇA BRUTA

Na implementação usando força bruta, serão testadas todas as variações de volume possíveis, em seguida, as