Algoritmos Gulosos

Algoritmos e Programação de Computadores II

Prof. MSc. Leanderson André

leandersonandre@univille.br

Universidade da Região de Joinville

Algoritmos Gulosos

Definição

Algoritmos Gulosos (do inglês, Greedy Algorithms) são uma Técnica de Design de Algoritmos que consiste em construir uma solução passo a passo, escolhendo, em cada etapa, a alternativa que parece ser a melhor naquele momento, sem reconsiderar as escolhas anteriores, com o objetivo de encontrar uma solução ótima para o problema.

Algoritmos Gulosos

Algoritmos gulosos utilizam a estratégia de low hanging fruit.

Algoritmos Gulosos

Importante

Não existem garantias que o algoritmo guloso irá encontrar a solução ótima do problema.

Problema do Troco

Algoritmo Guloso

Escolher sempre a maior moeda sem ultrapassar o valor alvo.

Exemplo: moedas = {1,2,5}, alvo = 12.

Escolhido a moeda: 5 (restante: 7)
Escolhido a moeda: 5 (restante: 2)
Escolhido a moeda: 2 (restante: 0)
Solução ótima encontrada: 3 moedas.

Problema do Troco

Algoritmo Guloso

Escolher sempre a maior moeda sem ultrapassar o valor alvo.

Exemplo: moedas = {1,3,4}, alvo = 6.

Escolhido a moeda: 4 (restante: 2)
Escolhido a moeda: 1 (restante: 1)
Escolhido a moeda: 1 (restante: 20)
Solução encontrada. 3 moedas
Solução ótima: 2 moedas ( 3 + 3).

Problema da Seleção de Atividades

Dado um conjunto de atividades = {a₁, a₂, …, a_n}, em que cada atividade possui um horário de início e término, encontre o maior subconjunto de atividades que podem ser realizadas sem que haja sobreposição de horários.

Problema da Seleção de Atividades

Exemplo: considere as seguintes atividades:

Atividade	Início	Término
A	1	4
B	3	5
C	0	6
D	5	7
E	8	9
F	5	9

Qual é o maior número de atividades que podem ser realizadas sem sobreposição de horários?

Problema da Seleção de Atividades

3 atividades

A (1–4) + D (5–7) + E (8–9)

Atividade	Início	Término
A	1	4
B	3	5
C	0	6
D	5	7
E	8	9
F	5	9

Problema da Seleção de Atividades

Algoritmo Guloso

Escolher sempre a atividade que termina primeiro, desde que não haja sobreposição com as atividades já selecionadas.

Problema da Mochila Fracionária

Dado um conjunto de itens = {i₁, i₂, …, i_n}, em que cada item possui um peso e um valor associado, e uma mochila com capacidade máxima de peso, determine a quantidade de cada item que deve ser colocada na mochila para maximizar o valor total transportado, permitindo que os itens sejam divididos em frações.

Problema da Mochila Fracionária

Exemplo: considere os seguintes itens e uma mochila com capacidade máxima de 50 kg:

Item	Peso (kg)	Valor (R$)	Valor por kg (R$/kg)
A	10	60	6
B	20	100	5
C	30	120	4

Qual é a melhor combinação de itens, considerando que eles podem ser divididos em frações, para maximizar o valor total transportado sem ultrapassar a capacidade da mochila?

Problema da Mochila Fracionária

Valor máximo: R$ 240,00

A (10 kg) + B (20 kg) + 2/3 de C (20 kg)

Item	Peso (kg)	Valor (R$)	Valor por kg (R$/kg)	Quantidade utilizada
A	10	60	6	100%
B	20	100	5	100%
C	30	120	4	66,67%

Capacidade utilizada: 50 kg

Valor total: R\$60 + R\$100 + R\$80 = R$ 240,00

Problema da Mochila Fracionária

Algoritmo Guloso

Escolher sempre o item com maior valor por unidade de peso (R$/kg), adicionando-o à mochila até atingir sua capacidade. Se não houver espaço suficiente para o próximo item, adicionar apenas a fração que couber.

Exercícios

Exercício 1

Dado o problema da seleção de atividades, crie a solução utilizando algoritmos gulosos.

Exercício 2

Dado o problema da mochila fracionária, crie a solução utilizando algoritmos gulosos.

Prof. MSc. Leanderson André

leandersonandre@univille.br

Universidade da Região de Joinville