AlgoritmoGuloso-PUCMINAS

Prévia do material em texto

Exercícios – Algoritmo Guloso 
 
Nome: Guilherme Rodrigues Neves 
 
1- 1. Definir a subestrutura ótima 
A. Definir quais subproblemas podem ser resolvidos de maneira ótima 
para alcançar a solução ótima do problema original total 
2. Definir o critério guloso 
A. Tipicamente, um dos “segredos” dos algoritmos gulosos é a escolha 
de como o conjunto de entrada será ordenado. 
B. Como será definido a melhor escolha local. 
3. Após uma sequência de decisões, uma solução para o problema é 
alcançada. 
A. Nessa sequência de decisões, nenhum elemento é examinado mais 
de uma vez: ou ele fará parte da solução, ou será descartado. 
 
2- Tipicamente algoritmos gulosos são utilizados para resolver problemas de 
otimização. O maior problema é que uma escolha que foi feita nunca é revista. 
 
3- Entrada: conjunto de moedas e troco x. 
Critério guloso: Selecionar a moeda com maior valor igual ou menor que o 
troco x. 
 
1. Seleciona a moeda com maior valor igual ou menor que o troco x 
2. Some as moedas selecionadas 
3. Se a soma for igual ao troco, prossiga para o próximo passo. Senão, volte ao 
passo 1 
4. A quantia de moedas separadas é o resultado 
 
4- Entrada: Receber a quantidade de litros de leite necessários e a lista 
completa de fornecedores. 
Critério guloso: selecionar fornecedor com o menor preço por litro de leite 
1. Selecionar a empresa com o menor preço por litro 
2. Se o estoque for maior que a quantidade necessária, comprar só o 
necessário 
3. Se for igual ao necessário, comprar todo o estoque 
4. Se for menor que o necessário, volte ao passo 1, pegando o próximo 
fornecedor com o menor preço por litro 
5. Somar os valores e dar o resultado. 
 
5- Entrada: Lista de M estábulos ocupados que serão vedados e N placas 
Critério guloso: Escolher o menor comprimento das placas para cobrir todos os 
celeiros com o menor custo possível. 
1. Pegar o menor comprimento de placa para cobrir a maior quantidade de 
placas seguidas 
2. Se a placa cobrir todos os celeiros ocupados, é a solução. 
3. Senão, volte ao passo 1 
4. Somar o custo das placas utilizadas e exibir, junto com o número de placas.