olá meu nome é lucas meu nome é letícia meu nome é brendon e nós vamos apresentar hoje o algoritmo golos para começar imaginemos a seguinte situação uma cafeteria pretende entregar o troco aos seus clientes da melhor maneira possível ou seja entregando mínimo de moedas necessário vamos supor que ao comprar um produto o cliente pagou r$1 75 centavos a mais que o valor necessário em seguida a atendente ele retorna o troco com sete moedas de 25 centavos uma situação incômoda para o cliente e para a empresa ea fim de evitar tal situação a empresa faz uma
atualização no software do caixa eletrônico inserindo um novo algoritmo que ele retorne o troco com o mínimo de mortes possível o nome de algoritmo é o algoritmo guloso um algoritmo guloso como o nome sugere sempre faz escolhas que parecem ser a melhor no momento e isso significa que faz a melhor escolha local na esperança que essa escolha leve para uma solução ótima global assumo que você tenha uma função objetiva que precisa ser otimizada maximizada ou minimizada em algum ponto um algoritmo gozo fazer escolha gulosas em cada passo para assegurar que a função objetivo é otimizar
o algoritmo guloso tem apenas uma chance de computar uma solução ótima ou seja ele nunca volta e é aberto a situação portanto aplicando o algoritmo no problema ele retornaria ao invés de sete moedas apenas três apesar de funcionar para determinadas situações o grito não é 100% seguro como dito anteriormente ele nunca volta reveste a solução o algoritmo funciona muito bem para o sistema de câmbio no brasil como áreas disponíveis no país porém se tivéssemos um conjunto mínimo de moedas de um centavo três centavos quatro centavos e cinco centavos e fosse necessário retornar sete centavos de
troco com seria solução dado pelo amorim o agrícola que sária pelos maiores números e depois iria para os menores então a resposta gerada pela gripe seria um é de cinco centavos e duas de um centavo somando três moedas no entanto a solução ótima nesse caso seria um é de 4 centavos uma moeda de 3 centavos somando assim duas moedas um exemplo apresentado o favorito não trabalharia da seguinte maneira colocar as moedas por ordem decrescente de valor ficando assim um real e cinqüenta centavos 25 centavos 10 centavos e cinco centavos após isso verificaria se cada moeda
poderia ser escolhida para somar o valor final então ao aplicar o algoritmo ele escolheria as moedas de um real e cinqüenta centavos e vinte e cinco centavos após isso o valor estaria completo e o algoritmo encerraria logo podemos saber o que o algoritmo nem sempre é eficaz já que ele faz as escolhas que parecem ser ótimas no momento e nunca retorna caso elas não sejam o exemplo citado anteriormente podia ser resolvido por um algoritmo criado especificamente para o problema esse algoritmo retornaria à quantidade possível de cada moeda levando em consideração apenas o câmbio brasileiro analisando
a complexidade do algoritmo temos 20 operações que ocorre uma única vez logo a complexidade do algoritmo é constante portanto o de um o problema poderia ser resolvido também com um algoritmo mais gostoso e que o tornaria um pouco mais genérico em que as moedas possíveis seriam armazenadas em um vetor e seria usada uma repetição para retornar a quantidade de cada moeda analisando a complexidade desse código temos operações que acontecem apenas uma vez e oito operações que ocorrem n vezes então somando todas as operações temos que a complexidade é de 8 n mais 11 como a
parte mais gostosa do algoritmo seria parte n então complexidade do algoritmo seria o dem tanto esse foi o algoritmo anguloso e espero que vocês tenham gostado e até uma próxima
