Imagine que você se depara com um problema da seguinte forma: você tem algumas cédulas na mesa e quer conseguir a maior quantidade de dinheiro pegando apenas 3 delas. A solução é simples certo? Basta ordenar as cédulas e pegar as 3 maiores. Esse tipo de técnica onde pegamos os maiores (ou os menores) de um grupo é comumente chamada de “algoritmo guloso” ou “ideia gulosa” e pode ser usado para resolver problemas bem mais complicados. Vamos ver o código de um exemplo de questão, parecida com a anterior.

Em uma cidade só há notas de 1, 10, 50, 100 e 500 reais. Qual a menor quantidade de notas que você precisa para formar um valor x? Vemos que nesse caso sempre vale mais a pena pegar a nota de maior valor possível já que os valores são múltiplos. Logo:

#include<iostream>
 
using namespace std;
 
int main()
{
	int a, s = 0;

	cin >> a;

	while(a >= 500)
	{
		a -= 500;
		s++;
	}
	
	while(a >= 100)
	{
		a -= 100;
		s++;
	}

	while(a >= 50)
	{
    	a -= 50;
    	s++;
	}

	while(a >= 10)
	{
		a -= 10;
		s++;
	}

	while(a >= 1)
	{
    	a -= 1;
    	s++;
 	}
 	
 	cout << s << "\n";
 
 	return 0;
}

A

Problemas:

• OBI – Fechadura

• OBI – Caverna de Ordinskaya

• URI – Apagando e Ganhando