AlgoritmoGuloso

Prévia do material em texto

PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS UNIDADE SÃO 
GABRIEL 
 
BACHAREL EM SISTEMAS DE INFORMAÇÃO 
 
 
 
 
 
 
 
 
 
Lista de exercício 
 
Técnicas Avançadas de Programação 
 
 
 
 
 
 
 
 
Aluno: João Victor Tavares Emilio 
Número de Matrícula: 668775 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
MARÇO 2021 
1. Apresente um esboço do esquema geral da Técnica de Projeto de 
Algoritmo Guloso. 
Resposta: 
1- Primeiramente vamos definir a subestrutura ótima: 
• Aqui vamos definir quais os SUB problemas podem ser resolvidos 
de maneira ótima na qual vai alcançar uma ótima solução do 
problema original. 
2- Apos isso vamos definir o critério guloso desse algoritmo: 
• Aqui podemos escolher como o conjunto de entrada vai ser 
ordenado, definindo assim a melhor escolha local. 
3- Apos essa sequência de decisões, vamos chegar a alguma solução para 
nosso problema: 
• Nessa sequencia nenhum elemento será analisado mais de uma 
vez, ou ele faz parte da nossa solução ou ele é removido. 
 
 
 
2. Considere os algoritmos baseados em Algoritmo Guloso. Quando eles 
são utilizados? 
 Qual é o principal problema que enfrentam os algoritmos gulosos? 
Resposta: 
O algoritmo guloso será usado quando a função de seleção será relacionada a 
função de objetivo, como achar o menor custo (minimizar) ou maximizar um ganho 
individual. O seu principal problema é que não será em todos os casos que ele 
vai encontrar a solução global ótima. 
 
 
3. Suponha que tenhamos disponíveis moedas com valores de 100, 25, 10, 5 
e 1. O problema é criar um algoritmo que para conseguir obter um 
determinado valor com o menor número de moedas possível (problema do 
troco). Escreva um Algoritmo Guloso para determinar uma solução do 
problema. Execute seu algoritmo e mostre o resultado para os seguintes 
valores: 55, 67, 23 e 141. 
 
 
 
 
Resposta: 
1- Primeiramente, nos vamos ordenar as moedas e definir a subestrutura 
ótima. Critério guloso: 
• Vamos selecionar a moeda com maior valor disponível, o valor da 
moeda não pode ser maior que o valor que foi selecionado; 
• Se a moeda for maior que o valor, vamos passar para a próxima 
maior moeda, e vamos repetir isso até que a moeda não seja maior 
que o valor; 
• Uma moeda pode se repetir e podemos usar outras moedas 
também, podemos fazer isso enquanto o nosso valor selecionado 
não for ultrapassado. Vamos repetir e escolher novas moedas até 
encontrar o valor. 
2- Vamos fazer para cada moeda agora: 
• Moeda valor 55: Aqui vamos comparar: 
o 55 não é menor que 100; 
o 55 é maior que 25; 
Vamos pegar então duas moedas com valor 25 que é a maior 
possibilidade, assim teremos 50 e resto 5, agora vamos pegar outra 
moeda para comparar ao troco: 
o 5 é menor que 100; 
o 5 é menor que 25; 
o 5 é menor que 10; 
o 5 é igual a 5; 
Vamos pegar então mais uma moeda de 5. A solução é pegar duas 
moedas de 25 e uma de 5 
 
• Moeda valor 67: Vamos comparar: 
o 67 não é menor que 100; 
o 67 é maior que 25: 
Vamos pegar então duas moedas de 25 que será a maior 
possibilidade, teremos assim 50, 50 – 67 terá um resto de 17, vamos 
pegar outras moedas para comparar com o troco: 
o 17 não é maior que 100; 
o 17 não é maior que 25; 
o 17 é maior que 10: 
Vamos pegar então uma moeda de 10 que será a maior 
possibilidade, teremos assim um total de 60, 60 – 67 terá um resto 
de 7, vamos pegar outras moedas para comparar com o troco: 
o 7 não é maior que 100; 
o 7 não é maior que 25; 
o 7 não é maior que 10; 
o 7 é maior que 5: 
Vamos pegar então uma moeda de 5 que será a maior possibilidade, 
teremos assim um total de 65, 65 – 67 terá um resto de 2, vamos 
pegar outras moedas para comparar com o troco: 
o 2 não é maior que 100; 
o 2 não é maior que 25; 
o 2 não é maior que 10; 
o 2 não é maior que 5; 
o 2 é maior que 1: 
Vamos pegar então duas moedas de 1. A solução é pegar duas 
moedas de 25, uma de 10, uma de 5 e duas de 1. 
 
• Moeda valor 23: Vamos comparar: 
o 23 é menor que 100; 
o 23 é menor que 25; 
o 23 é maior que 10: 
Vamos pegar então duas moedas de 10 que será a maior 
possibilidade, teremos assim um total de 20, 23 - 20 terá um resto 
de 3, vamos pegar outras moedas para comparar com o troco: 
o 3 é menor que 100; 
o 3 é menor que 25; 
o 3 é menor que 10; 
o 3 é menor que 5; 
o 3 é maior que 1: 
Vamos pegar então três moedas de 1. A solução é pegar duas 
moedas de 10 e três de 1. 
 
• Moeda valor 141: Vamos comparar: 
o 141 é maior que 100: 
Vamos pegar então uma moeda de 100 que será a maior 
possibilidade, teremos assim um total de 100, 141 – 100 terá resto 
de 41, vamos pegar outras moedas para comparar com o troco: 
o 41 é menor que 100; 
o 41 é maior que 25: 
Vamos pegar então uma moeda de 25 que será a maior 
possibilidade, teremos assim um total de 125, 141 – 125 terá resto 
de 16, vamos pegar outras moedas para comparar com o troco: 
o 16 é menor que 100; 
o 16 é menor que 25; 
o 16 é maior que 10: 
Vamos pegar então uma moeda de 10 que será a maior 
possibilidade, teremos assim um total de 135, 141 – 135 terá resto 
de 6, vamos pegar outras moedas para comparar com o troco: 
o 6 é menor que 100; 
o 6 é menor que 25; 
o 6 é menor que 10; 
o 6 é maior que 5: 
Vamos pegar então uma moeda de 5 que será a maior possibilidade, 
teremos assim um total de 140, 141 – 140 terá resto de 1, vamos 
pegar outras moedas para comparar com o troco: 
o 1 é menor que 100; 
o 1 é menor que 25; 
o 1 é menor que 10; 
o 1 é menor que 5; 
o 1 é igual a 1: 
Vamos pegar então uma moeda de cada, uma de 100, uma de 25, 
uma de 10, uma de 5 e uma de 1. 
 
 
 
4. A empresa KeroLeite precisa comprar N litros de leite por dia. A empresa 
tem M possíveis fornecedores. Cada fornecedor tem um limite de produção 
de leite ci e preço por litro pi, 1 ≤ i ≤ M. Queremos comprar N litros com o 
menor custo possível. Escreva um Algoritmo Guloso para determinar uma 
solução do problema. Execute seu algoritmo e mostre o resultado quando a 
demanda da empresa é de 100 litros de leite. O número de fornecedores é 5. 
A lista de fornecedores segue abaixo com o preço por litro e a sua produção: 
 
 
 
 
 
 
Resposta: 
1. Primeiro nos vamos dar nosso critério guloso: vamos pegar empresas de 
menor preço por litro e comprar com ela até não podermos mais (no caso 
até aonde a produção dela suportar), quando não der mais para usar essa 
empresa escolheremos outra com menor preço de produção, vamos fazer 
isso até comprar toda a quantidade de leite necessário. 
• Valor de N igual a 100: 
• Vamos pegar a empresa com menor preço do litro: 
o Empresa 3, preço do litro = 3, produção 10 
• Agora pegamos a empresa com próximo menor valor: 
o Empresa 1, preço do litro = 5, produção 20 
o Temos um total de 30 litros 
• Agora pegamos a empresa com próximo menor valor: 
o Empresa 5, preço do litro = 6, produção 30 
o Total de 60 litros 
• Agora pegamos a empresa com próximo menor valor: 
o Empresa 4, preço do litro = 8, produção 80 (nesse caso 
precisamos apenas de 40 pois já temos 60 litros) 
o Total de 100 litros. 
 
5. Problema Consertando o Celeiro: Temos uma longa lista de M estábulos 
ocupados que devem ser vedados com placas. Você pode usar até N placas, 
uma placa pode cobrir qualquer número de cocheiras consecutivas depende 
apenas do seu comprimento. Você escolhe o comprimento da placa, mas a 
placa não pode ser cortada. O custo da placa é igual ao comprimento da 
placa. Cubra todas as cocheiras ocupadas, com o menor custo possível. 
Como resolver o problema usando Algoritmo Guloso? 
• Exemplifique a utilizando do seu algoritmo levando em consideração o 
seguinte cenário: -- O número de placas que podem ser encomendadas são 
4. O número máximo de celeiros é 50. O número de estábulos ocupados é 
18. Os seguintes celeiros estão ocupados: 3 4 6 8 14 15 16 17 21 25 26 27 30 
31 40 41 42 43. 
Resposta: 
 
1. Primeiramente, vamos criar nosso critérioguloso: 
• Vamos considerar que esses 18 valores então em um vetor, o 
algoritmo vai passar por todas as posições e subtrair o próximo valor 
pelo atual valor do vetor selecionado, dessa forma vamos achar as 
três distâncias que não vão precisar de placas. Nós também vamos 
armazenar essas posições; 
2. Agora o algoritmo vai colocar a placa do primeiro valor do vetor (3 que 
é o primeiro do nosso vetor) até o valor da nossa primeira separação 
(8): 
• O comprimento da placa será de 8 - 3 +1 = 6 
3. Agora vamos para a placa de número 14 até a 17: 
• O comprimento da placa será de 14 – 17 + 1 = 4 
4. Vamos para a próxima placa de 21 a 31: 
• O comprimento da placa será de 21 – 31 + 1 = 11 
5. Nossa última placa vai começar do 40 até o 43 
• O comprimento da placa será de 40 – 43 + 1 = 4 
6. O resultado é 4 placas com os respectivos comprimentos: 6, 4, 11 e 4.