Algoritmos GulososTroco Mínimo

Gabriel RamalhoTúlio Lemes

Vinicius Rodrigues

1.1 Definição do Problema: Dado a necessidade de representar um certo valor (troco) com o menor número de moedas possível, utilizamos algoritmos gulosos para buscar soluções ótimas (o que nem sempre ocorre).

Podemos tomar como exemplo eventos da vida real:

● Caixas de bancos e estabelecimentos comerciais freqüentemente trabalham com a tarefa de produzir troco, procurando fazê-la da maneira mais eficiente possível.

1. Motivação

Dado os tipos de moedas de um país, determinar o número mínimo de moedas para dar um troco de valor n.

1.2 Descrição Informal:

Questão: Dado K denominações de moedas M[k] = { m1, m2, m3,..., mk }, tal que m1< m2 < ... < mk e supondo um troco para n, encontre uma solução C[n] = x1m1 + x2m2 + ... + xkmk, tal que x1 + x2 + ... + xk seja o menor possível.

Entrada:● M[k] = {m1, m2, m3, …, mk} (conjunto de moedas)● Valor a ser gerado pelas moedas = n● Quantidade de moedas = k

Saída: Quantidade de moedas utilizadas para gerar o troco.

1.3 Descrição Formal:

Suponha que é preciso “dar um troco” de $289,00 e temos disponíveis moedas com valores de 100, 50, 25, 5 e 1

Menor número de moedas possível:2 de valor 1001 de valor 501 de valor 252 de valor 54 de valor 1

De forma geral, agimos tal como um algoritmo guloso: em cada estágio adicionamos a moeda de maior valor possível, de forma a não passar da quantia necessária.

1.4 Exemplo:

Moedas = {1, 5, 25, 50, 100}Tamanho do Vetor = 5 Troco = 289Total de Moedas= 0

1.4.1 Exemplo:

Tamanho do Vetor = i = 5

⌊ ( Troco/Moedas[i] ) ⌋ = ⌊ ( 289/100 ) ⌋ = 2Troco = 289 - ( ⌊ ( 289/100 ) ⌋ * 100) = 289 - 200 = 89Total de Moedas = ⌊ ( 289/100 ) ⌋ = 2

1.4.1 Exemplo:

Tamanho do Vetor = i = 4

⌊ ( Troco/Moedas[i] ) ⌋ = ⌊ ( 89/50 ) ⌋ = 1Troco = 89 - ( ⌊ ( 89/50 ) ⌋ * 50) = 89 - 50 = 39Total de Moedas = 2 + ⌊ ( 89/50 ) ⌋ = 2 + 1 = 3

1.4.1 Exemplo:

Tamanho do Vetor = i = 3

⌊ ( Troco/Moedas[i] ) ⌋ = ⌊ ( 39/25 ⌋ = 1Troco = 39 - ( ⌊ ( 39/25 ) ⌋ * 25) = 39 - 25 = 14Total de Moedas = 3 + ⌊ ( 39/25 ) ⌋ = 3 + 1 = 4

1.4.1 Exemplo:

Tamanho do Vetor = i = 2

⌊ ( Troco/Moedas[i] ) ⌋ = ⌊ ( 14/5 ⌋ = 4Troco = 14 - ( ⌊ ( 14/5 ) ⌋ * 5) = 14 - 10 = 4Total de Moedas = 4 + ⌊ ( 14/5 ) ⌋ = 4 + 2 = 6

1.4.1 Exemplo:

Tamanho do Vetor = i = 1

⌊ ( Troco/Moedas[i] ) ⌋ = ⌊ ( 4/1 ⌋ = 4Troco = 4 - ( ⌊ ( 4/1 ) ⌋ * 1) = 4 - 4 = 0Total de Moedas = 6 + ⌊ ( 4/1 ) ⌋ = 6 + 4 = 10

1.4.1 Exemplo:

Mas, nem sempre essa estratégia funciona, por exemplo:

Suponha que e preciso “dar um troco” de $20,00 e temos disponíveis moedas com valores de 100, 50, 24, 12, 5, 1

Usando a estratégia anterior:1 de valor 121 de valor 53 de valor 1

O que é errado, pois é possível dar um troco utilizando 4 moedas de valor 5.

1.4.2 Exemplo:

2. Algoritmo// d é um vetor com os valores das moedas, ordenado do maior para o menor// k é a quantidade de elementos nesse vetor// n é o valor do trocoFunção Troco(d, k, n) S <- 0 // número mínimo de moedas (solução ótima) s <- [] // vetor que irá guardar a quantidade de moedas utilizadas para cada valor do vetor S i <- 0 enquanto i < k, faça: s[i] <- ⌊n / d[i]⌋ // divide o troco pelo valor da moeda atual n <- n - s[i] * d[i] // diminui do valor do troco, o valor parcial S <- S + s[i] // incrementa S com a quantidade de moedas utilizadas

i <- i + 1 fim enquanto retorne S

Quando o método guloso funciona, o algoritmo é, em geral, eficiente.

Figurativamente, a solução gulosa consiste em, a cada passo, escolher o melhor pedaço possível e não se arrepender.

Para saber se o método guloso funciona, é necessário provar que o algoritmo resolve o problema.

3. Análise do Algoritmo

Porque o método funciona para o seguinte conjunto de moedas?

M = [1, 5, 10, 25, 50, 100]

3. Análise do Algoritmo

1. A tabela abaixo mostra o máximo de moedas de cada tipo usado em um troco mínimo, pois, para cada aumento nesses valores, existe outra opção com menos moedas. Adicionalmente, não se pode usar simultâneamente 2 moedas de 10 e 1 de 5.

3. Análise do Algoritmo

1 5 10 25 50 100

4 1 2 1 1 ∞

2. O valor máximo conseguido com as moedas tipos 1 a 5 é 99. Logo, qualquer troco x > 99 usa tantas moedas de 100 quanto necessário.

3. O valor máximo conseguido com as moedas tipos 1 a 4 é 49. Logo, qualquer troco x, 100 > x > 49, usa 1 moeda de 50.

4. O valor máximo conseguido com as moedas tipos 1 a 3 é 24. Logo, qualquer troco x, 50 > x > 24, usa 1 moeda de 25.

5.O valor máximo conseguido com as moedas tipos 1 e 2 é 9. Logo, qualquer troco x, 25 > x > 9, usa 1 ou 2 moedas de 10.

3. Análise do Algoritmo

6. O valor máximo conseguido com as moedas do tipo 1 é 4. Logo, todo valor x, 10 > x > 4 usa 1 moeda de 5.

Conclusão: o troco mínimo obtido pelas considerações anteriores é exatamente aquele obtido com o algoritmo guloso. Logo, o método guloso funciona corretamente para esse conjunto de moedas.

3. Análise do Algoritmo

3.1 Prova de Corretude:•Consideremos S={s1,s2,...,sx} um conjunto com todas moedas utilizadas para gerar uma solução ótima obtida a partir do algoritmo, cujas moedas são {1, 5, 25, 50, 100}.

• Por contradição, assuma a existência de outra solução chamada S′={s′1, s′2,...,s′y}

• S′ possui um menor número de moedas que S.

3. Análise do Algoritmo

•q → nº de moedas de um determinado valor em S.

•q′ → nº de moedas de um determinado valor em S′.

•Usando q(100) e q’(100), e supondo que troco > 100, podemos concluir que:

troco = (q(100) * 100) + r, r < 100

•Logo, se considerarmos que q’(100) < q(100):

troco = (q’(100) * 100) + r’, r’ >= 100

3.1 Prova de Corretude

•Podemos afirmar que esta não é uma solução ótima, pois se r’ é maior que 100, haveria a chance de q’(100) ser acrescido.

•Analogamente podemos considerar as quantidades de moedas menores.

troco = (q’(100) * 100) + (q’(50) * 50) + ... + (q’(1) * 1) + r’ r’ >= 1

3.1 Prova de Corretude

•Isto é absurdo, pois r’ não pode ser maior ou igual a 1 tendo em vista que a soma de todas as moedas utilizadas já equivale ao troco desejado, ou seja:

troco = (q’(100) * 100) + (q’(50) * 50) + ... + (q’(1) * 1)

•Se considerarmos q = q’, também será uma situação absurda, pois os somatórios das quantidades de moedas de q, e de q’ nunca serão iguais, já que S > S’, ficando provado que S’ não existe.

3.1 Prova de Corretude

•Nem sempre é possível afirmar que o algoritmo guloso fornece uma solução ótima, para todos os conjuntos de moedas. Exemplo:• Moedas = {1, 7, 15, 20} Troco = 31 S = {20, 7, 1, 1, 1, 1}

•Esta solução não é ótima, pois existe S’ = {15, 15, 1}

3.1 Prova de Corretude

O algoritmo possui uma interação de k até 1. Desta forma, a função que representa a complexidade do algoritmo é:

Onde c representa uma constante referente aos passos realizados dentro do comando de repetição. Assim, procedendo à análise assintótica do problema temos que:

3. Complexidade

Conclusão:Vantagens:● Rápido e Eficiente● Simples e de fácil implementação

Desvantagens:● Nem sempre fornece uma solução ótima● Não reconsidera uma solução tomada

Conclusão:● Complexidade de O(n)● Programação dinâmica é melhor

Bibliografia:● http://www.ime.uerj.br/~pauloedp/ALGO/Download/ALSLGULO.pdf● http://www.ic.unicamp.br/~rocha/msc/complex/algoritmosGulososFinal.pdf● http://wpattern.com/blog/post/2012/03/24/Problema-do-Troco-Analise-de-

Algoritmos.aspx● https://docs.google.com/presentation/d/1LHv2ymwaCh8xeyZ2X170IU-

WnCkUBZ75IClAjs0-_XM/edit#slide=id.p32