Aula de Rogério Júnior
Imagine o seguinte problema: você é o dono de uma grande rede de postos de gasolina e, ao final do mês, você renova seu estoque. Nesse dia, o setor de pesquisa da sua empresa lhe envia uma lista com os preços e estoques dos seus maiores fornecedores. A primeira linha da lista tem um inteiros n e um decimal d, o número de fornecedores e a demanda do mercado, respectivamente. Cada uma das próximas n linhas tem dois decimais: 
e 
, respectivamente. Na i-ésima linha, é o preço do litro de gasolina no fornecedor 
e é o estoque desse fornecedor em litros. Você deseja comprar exatamente a demanda que precisa (para que seu lucro seja máximo pela lei da oferta e da procura), então faça um programa que calcule quanto dinheiro você irá gastar nessa compra de modo que o custo seja mínimo, e imprima esse valor com precisão de duas casas decimais. Se não houver estoque suficiente no mercado para a sua compra, imprima uma única linha com a palavra "Impossivel".
A primeira ideia que podemos ter é ordenar os fornecedores pelos preços de seus combustíveis, do menor para o maior comprar o máximo possível do fornecedor mais barato e então passarmos para o fornecedor seguinte (o próximo mais barato) até que tenhamos comprado toda a demanda necessária. Felizmente essa ideia realmente funciona e é eficiente! Ela funciona porque se terminarmos as compras e sobrar gasolina em um fornecedor A que é mais barato que algum fornecedor B em que você comprou, o preço final teria sido menor se você tivesse comprado a gasolina de A ao invés da de B. Ordenar os fornecedores pelo preço da gasolina custa O(n*log n), e percorrer o vetor comprando a gasolina leva O(n). Assim a complexidade fica O(n*(log n+1)) 
O(n*log n).
Para facilitar o código, criei a struct gas, que guarda duas doubles: preco e estoq, representando um fornecedor. Depois crio o array de gas de nome forn para representar a lista de fornecedores que você recebeu do setor de pesquisa, e é esse array que vou ordenar com o sort e a função compara, que faz a comparação entre dois gas pelos valores de suas variáveis preco. Ao percorrer o vetor, vou comprando a gasolina mais barata sempre e guardando o valor gasto na variável custo. No final, imprimo o valor gasto com precisão de duas casas decimais Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <algorithm> | |
| #define MAXN 100100 | |
| using namespace std; | |
| struct gas{ double preco, estoq; }; // declaro a struct gas | |
| bool compara(gas x, gas y){ return x.preco < y.preco; } // declaro a bool compara | |
| gas forn[MAXN]; // crio um array de gas de nome "forn" para representar a lista | |
| // declaro as variáveis que vou usar | |
| int n; | |
| double d, custo; | |
| int main(){ | |
| scanf("%d %lf", &n, &d); // leio os valores de n e d | |
| // leio o preço e eo estoque de cada fornecedor | |
| for(int i=1; i<=n; i++) scanf("%lf %lf", &forn[i].preco, &forn[i].estoq); | |
| // ordeno o veotor de gas | |
| sort(forn+1, forn+n+1, compara); | |
| // percorro o vetor | |
| for(int i=1; i<=n; i++){ | |
| // o fornecedor davez será o que estou olhando no vetor, no momento | |
| gas davez=forn[i]; | |
| // se todo o seu estoque não consegue preencher o que ainda preciso | |
| if(davez.estoq<d){ | |
| custo+=davez.estoq*davez.preco; // somo a custo o valor de comprar todo o estoque | |
| d-=davez.estoq; // e subtraio de d o litros que comprei | |
| } | |
| // caso contrário, ou seja, dá pra encher tudo só com esse fornecedor | |
| else{ | |
| custo+=d*davez.preco; // somo acusto o valor de comprar o que preciso | |
| d=0; // zero a quantidade que a inda falta comprar | |
| break; // e paro de percorrer o vetor, pois já comprei o que precisava | |
| } | |
| } | |
| // se o loop acabar e ainda houver alguma quantidade em d | |
| if(d) printf("Impossivel\n"); // então não foi possível comprar tudo o que precisava | |
| // caso contrário, foi possível | |
| else printf("%.2lf\n", custo); // e imprimo o valor gasto na compra | |
| return 0; | |
| } |
Este programa resume muito bem a ideia de um algoritmo guloso: é aquele em que temos que fazer algumas escolhas, então ordeno as opções usando o critério de comparação que parece o melhor possível para a escolha desejada, e depois vou escolhendo as melhores opções até que tenha feito tudo o que preciso. No caso, tenho que escolher de quais fornecedores comprar, então ordeno as opções pelo critério preço, pois o melhor fornecedor é o mais barato, e vou comprando sempre do melhor até que tenha atingido a demanda necessária.
Um programa que vai procurando as melhores opções no momento, é um programa guloso, e este tipo de algoritmo resolve muitos problemas. O problema mais difícil que já caiu na PJ pode ter sido o Dentista, da OBI 2010. Agora que você já sabe como implementar um algoritmo guloso, clique aqui para tentar resolvê-lo. Se você não conseguir, seguem a resposta e o código comentado, mas realmente tente fazê-lo sozinho antes de os ler.
O dentista quer sempre atender à consulta que conflitua com o menor número de consultas que ele ainda pode pegar. Como ordenar, então as escolhas? Parece bem atrativo escolhermos sempre as consultas de menor duração que não conflituam com as já escolhidas, mas veja o seguinte caso: tenho uma consulta que começa às 9 e termina às 12 (três horas de duração), uma que começa às 11 e termina às 13 (duas horas de duração) e uma que começa às 12 e termina às 15 (três horas de duração). Note que é melhor escolher as duas consultas mais longas do que escolher a curta, pois elas são conflitantes. Ponha-se então no lugar do dentista: você acabou de atender um paciente e na sala de espera estão todas as pessoas cujo horário do começo da consulta ainda não passou, qual delas você atenderia? A que termina primeiro! Qualquer outra consulta que termine um pouco mais tarde pode acabar conflituando com alguma outra que você poderia atender se tivesse pego a consulta que termina mais cedo! Assim, faremos um guloso que ordena as consultas por fim e vamos sempre atender a consulta (que ainda pode ser atendida, ou seja, que não passou ainda o horário do começo) que termina mais cedo.
Vamos criar a struct compromisso, que guarda os inteiros ini e fim. Vamos criar um vetor de compromissos de nome consulta e, em cada um de seus elementos, guardar os horários de início e fim de cada consulta. Vamos ordenar o vetor pelo valor de fim de cada elemento e percorrê-lo guardando em livre, o horário em que o dentista já poderá atender o próximo cliente. No começo, livre será zero. Percorrendo o vetor, para cada elemento olharemos se podemos atender a consulta (se seu começo é depois de livre). Se pudermos, adicionamos um a qtd, que guardará o número de consultas atendidas, e faremos livre receber o fim da consulta que estamos verificando. Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <algorithm> | |
| #define MAXN 10100 | |
| using namespace std; | |
| struct compromisso { int ini, fim; }; // declaro a sruct compromisso | |
| // declaro a função que compara compromissos pelo horário de fim | |
| bool compara(compromisso a, compromisso b){ return a.fim<b.fim; } | |
| compromisso consulta[MAXN]; // crio o vetor de compromissos de nome consulta | |
| int n, x, y, livre, qtd; // declaro os inteiros que vou usar | |
| int main(){ | |
| scanf("%d", &n); // leio o valor de n | |
| // leio os horários de início e fim de cada consulta | |
| for(int i=1; i<=n; i++) scanf("%d %d", &consulta[i].ini, &consulta[i].fim); | |
| // ordeno as consultas pelo horário de fim | |
| sort(consulta+1, consulta+n+1, compara); | |
| // percorro o vetor ordenado | |
| for(int i=1; i<=n; i++) // para cada consulta | |
| if(consulta[i].ini>=livre){ // se posso atendê-la | |
| qtd++; // aumento o número de atendimentos | |
| livre=consulta[i].fim; // e guardo a hora em que o dentista estará livre | |
| } | |
| printf("%d\n", qtd); // por fim, imprimo o valor de qtd | |
| return 0; | |
| } |
Novamente, temos a implementação geral de um algoritmo guloso: tenho que fazer um conjunto de escolhas; crio um critério de ordenação para elas, que decide qual a melhor a ser tomada; ordeno as escolhas por esse critério; percorro as possíveis escolhas, da melhor para a pior, sempre escolhendo as possíveis, com prioridade para as melhores, até já ter atingido meu objetivo.
Agora que você já sabe tudo isso, tente resolver os problemas abaixo. Se você não conseguir resolver algum deles ou surgir uma dúvida na explicação teórica, volte para a página inicial do curso e preencha o formulário para nos enviar sua dúvida.
Problema 1 - Comércio de Vinhos na Gergóvia
Problema 2 - Concurso de Contos
Problema 3 - Station Balance
Problema 4 - All in All
Problema 5 - Ferry Loading II
Problema 6 - Work Reduction
Problema 7 - Foreign Exchange
Problema 8 - Dragon of Loowater
Problema 9 - Shopaholic
Problema 10 - Minimal Coverage (Se não conseguir, não se preocupe, pois ele usa ideias de um paradigma ainda não tratado no curso: o Sweep Line)
As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.