Aula 12 - Algoritmo Guloso

2 Flares Facebook 2 2 Flares ×

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 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: p_i e e_i, respectivamente. Na i-ésima linha, p_i é o preço do litro de gasolina no fornecedor ip_i é 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 doublesprecoestoq, 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:

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 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:

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.

2 Flares Facebook 2 2 Flares ×
2 Flares Facebook 2 2 Flares ×
%d bloggers like this: