Projeto 1: exercícios validados

Escolha do problema

• Cada grupo escolhe somente um problema e desenvolve apenas a opção escolhida.
• Dois grupos não podem escolher o mesmo problema. A escolha será registrada com o professor durante a apresentação das opções à turma.

Use a tabela para localizar a opção escolhida e leia sua seção completa. A linguagem e as bibliotecas são livres. As estruturas e técnicas indicadas devem participar efetivamente da solução, mas o grupo pode adaptar implementações estudadas nas aulas. Uma coleção baseada em vetor não substitui uma estrutura encadeada quando o enunciado exigir encadeamento.

Opção	Problema	Conteúdo central
1	Robô de inspeção em um armazém	Fila encadeada e expansão por distância
2	Colorização automática de regiões	Pilha encadeada e uma cor por região
3	Colorização automática por camadas	Fila encadeada e lista circular de cores com representação livre
4	Dispensador automático	Programação dinâmica e reconstrução
5	Montagem automática de escala	Backtracking e poda por inviabilidade
6	Seleção de sensores para uma estação remota	Branch-and-bound e poda por limite
7	Redução de uma suíte de testes	Força bruta e estratégia gulosa
8	Substituição em cache com acessos conhecidos	Estratégia gulosa e comparação com fila FIFO
9	Equivalência de regras booleanas	Força bruta e pilha encadeada
10	Circuito mínimo de visita	Branch-and-bound sobre ordens de visita
11	Sequenciamento com penalidade de atraso	Branch-and-bound sobre ordens de execução
12	Seleção de equipamentos para uma expedição	Mochila 0/1 com programação dinâmica e reconstrução

Boa prática interna: recomenda-se que cada grupo registre como compilar e executar seu programa. Essa documentação serve somente para a organização dos integrantes e não precisa ser apresentada nem entregue ao professor.

Opção 1: robô de inspeção em um armazém

Objetivo

Implemente uma simulação que encontre uma rota com a menor quantidade de movimentos entre a posição inicial de um robô e um ponto de inspeção. Prateleiras e áreas interditadas impedem a passagem.

O projeto simula o deslocamento em software. Não é necessário construir ou controlar um robô físico.

Modelagem do problema

Represente o armazém por uma matriz com L linhas e C colunas. Cada posição (l, c) contém uma célula livre ou um obstáculo.

Duas células são vizinhas quando compartilham um lado. Portanto, a partir de (l, c), os únicos movimentos possíveis são (l - 1, c), (l + 1, c), (l, c - 1) e (l, c + 1), desde que a nova posição permaneça dentro da matriz e esteja livre.

Uma rota válida é uma sequência de células livres que começa na origem, termina no destino e usa somente movimentos entre células vizinhas. O custo da rota é a quantidade de movimentos, equivalente à quantidade de transições entre células consecutivas. O programa deve minimizar esse custo.

Use uma fila encadeada para organizar as posições pendentes em ordem não decrescente de distância à origem. Cada posição deve entrar na fila no máximo uma vez.

Entrada

Use, no mínimo, o seguinte modelo de dados:

• L e C, com valores entre 1 e 30;
• uma matriz com L linhas e C colunas;
• uma coordenada de origem;
• uma coordenada de destino.

No formato textual de referência, . representa uma célula livre e # representa um obstáculo. As coordenadas começam em zero, (0, 0) identifica o canto superior esquerdo, a linha aumenta para baixo e a coluna aumenta para a direita.

5 7
.......
...#...
...#...
...#...
.......
2 0
2 6

A origem e o destino devem estar dentro da matriz e sobre células livres.

Regras essenciais

• O robô pode mover uma célula para cima, para baixo, para a esquerda ou para a direita. Movimentos diagonais são proibidos.
• Cada movimento custa uma unidade. O robô não pode atravessar obstáculos nem sair da matriz.
• O mapa permanece fixo durante a busca.
• A fila usada na expansão deve ser explicitamente encadeada.
• A solução pode apresentar qualquer rota mínima quando houver empate.
• Quando origem e destino coincidirem, a rota possui zero movimentos.
• Quando não existir rota, o programa deve informar essa condição sem apresentar um percurso parcial como resposta.

Saída obrigatória

Mostre o mapa com a rota identificada e informe a quantidade de movimentos. A exibição pode usar caracteres no terminal, desde que origem, destino, obstáculos, rota e posições livres permaneçam distinguíveis.

Para a entrada de referência, uma saída válida contém uma rota com 10 movimentos. Outra rota também será aceita se respeitar o mapa e possuir o mesmo custo mínimo.

Exemplo visual de entrada e saída

No exemplo, S identifica a origem (2, 0), D identifica o destino (2, 6) e os blocos escuros representam obstáculos. A saída destaca uma das rotas mínimas: o robô contorna os obstáculos pela parte superior e chega ao destino após 10 movimentos.

Casos para verificar

• Um mapa com obstáculos, desvios e mais de uma rota possível: confira que o percurso escolhido é mínimo.
• Um destino separado da origem por obstáculos: confira a indicação de ausência de rota.
• Origem e destino iguais: confira o resultado com zero movimentos.

Limite do projeto

Considere um robô e um destino por execução. Não são exigidos múltiplos pontos de visita, obstáculos em movimento, custos variáveis, animação ou representação explícita do mapa como grafo.

Opção 2: colorização automática de regiões

Objetivo

Implemente um programa que pinte automaticamente as regiões brancas de um desenho. Cada região inteira deve receber uma única cor pseudoaleatória. Use uma pilha encadeada para controlar a expansão da pintura.

Modelagem do problema

Represente a imagem por uma matriz de pixels. Cada pixel de entrada é exatamente preto ou branco.

Considere dois pixels brancos conectados quando existe entre eles uma sequência formada somente por pixels brancos e movimentos para cima, para baixo, para a esquerda ou para a direita. Pixels que se tocam apenas pela diagonal não estão conectados por esse contato.

Uma região é um conjunto máximo de pixels brancos conectados. A palavra máximo significa que nenhum outro pixel branco pode ser acrescentado ao conjunto pelas regras de conexão. A saída deve manter os pixels pretos e substituir todos os pixels brancos de uma mesma região por uma única cor válida.

Use uma pilha encadeada para armazenar os pixels pendentes da região atual. A próxima posição processada deve ser a última inserida. Termine uma região antes de iniciar a seguinte.

Entrada

O programa deve receber o caminho de um arquivo PNG de entrada e o caminho do arquivo PNG de saída. A imagem deve ser opaca, possuir dimensões positivas e conter somente pixels pretos ou brancos.

Verifique essas propriedades depois de decodificar a imagem. A codificação interna do PNG pode usar, por exemplo, escala de cinza, RGB, RGBA ou paleta indexada. Não rejeite um arquivo somente pela forma como o PNG armazena as cores. Ele é válido para este problema quando os pixels decodificados são opacos e cada pixel resulta exatamente em preto ou branco. Qualquer transparência torna a entrada inválida, inclusive quando ela estiver definida na paleta, em vez de aparecer em um canal alfa separado.

O formato de execução de referência é:

programa entrada.png saida.png [semente]

A semente pseudoaleatória é opcional e, quando usada, deve ser um inteiro entre 0 e 4.294.967.295. Repetir a execução com a mesma imagem e a mesma semente deve produzir as mesmas cores.

Cada cor pode ser representada por três componentes RGB inteiros entre 0 e 255. Preto corresponde a (0, 0, 0) e branco corresponde a (255, 255, 255). Para os testes iniciais, o programa deve aceitar imagens de até 128 por 128 pixels.

Apoio opcional: o exemplo de leitura, alteração de pixels e gravação recebe uma imagem, altera seus pixels e salva um arquivo PNG. Baixe também os demais arquivos da pasta de suporte de imagens, incluindo a pasta vendor. O exemplo está em C, mas a linguagem da solução permanece livre.

Regras essenciais

• Preserve todos os pixels pretos.
• Pinte todos os pixels brancos, inclusive os localizados nos limites da imagem.
• Todos os pixels da mesma região devem receber a mesma cor.
• A cor deve ser diferente de preto e branco.
• Regiões diferentes podem receber a mesma cor.
• Ao consultar vizinhos, considere somente coordenadas existentes na matriz.
• Cada pixel deve entrar na pilha no máximo uma vez.
• A pilha deve ser explícita e encadeada. Usar somente chamadas recursivas não atende a esta opção.
• Se o arquivo não cumprir o contrato de entrada, informe o motivo e não produza uma imagem parcial como resultado.

Saída obrigatória

Salve no caminho solicitado uma imagem PNG colorida com as mesmas dimensões da entrada. Informe no terminal a quantidade total de regiões pintadas e preserve todos os pixels pretos.

Como as cores podem ser pseudoaleatórias, duas execuções podem produzir cores diferentes. O número de regiões, a separação entre elas e os pixels preservados devem permanecer iguais.

Casos para verificar

• Uma região com formato irregular: confira que toda a região recebe uma única cor e que a pintura não atravessa pixels pretos.
• Várias regiões, incluindo pixels que se tocam apenas pela diagonal: confira a separação correta.
• Uma região que alcança algum limite da imagem: confira que todos os pixels brancos conectados são pintados sem acessar posições externas à matriz.

Exemplos de entrada e saída

As cores das saídas são ilustrativas. Outra saída é válida se preservar os pixels pretos, pintar cada região inteira com uma única cor permitida e informar a mesma quantidade de regiões.

Caso	Entrada binária	Exemplo de saída válida
Região irregular
Contato diagonal
Região na borda

Limite do projeto

Use imagens binárias preparadas, sem pixels cinza e sem transparência. Não são exigidos reconhecimento de objetos, classificação de fundo ou cores diferentes entre regiões vizinhas.

Opção 3: colorização automática por camadas

Objetivo

Implemente um programa que pinte as regiões brancas de um desenho com camadas de cores que se repetem conforme a distância ao início da região. Use uma fila encadeada para expandir a pintura e uma lista circular de cores, com representação livre, para organizar a paleta.

Modelagem do problema

Represente a imagem por uma matriz de pixels pretos e brancos. Dois pixels brancos são vizinhos quando compartilham um lado, isto é, quando um está imediatamente acima, abaixo, à esquerda ou à direita do outro. Cada conjunto máximo de pixels brancos conectados por esses movimentos forma uma região. Contato apenas diagonal não conecta pixels.

Localize as regiões percorrendo as linhas de cima para baixo e, em cada linha, as colunas da esquerda para a direita. O primeiro pixel branco ainda não pintado encontrado nessa varredura será o início s da região.

Para cada pixel p da região, defina d(p) como a menor quantidade de movimentos válidos entre s e p, sem sair da região. Se a paleta ordenada contém m cores, numere suas posições de 0 a m - 1. Escolha a posição da cor por d(p) mod m.

mod significa resto da divisão inteira. Com três cores, os restos possíveis da divisão por 3 são 0, 1 e 2. Por isso, as distâncias 0, 1 e 2 usam as três cores, a distância 3 volta à posição 0, a distância 4 usa a posição 1 e o ciclo continua.

Use uma fila encadeada para processar os pixels por distância. A paleta deve se comportar como uma lista circular: depois da última cor, volte à primeira. Sua representação interna é livre e não precisa ser encadeada. Reinicie o uso da paleta na primeira cor ao começar cada região.

Entrada

O programa deve receber, nesta ordem:

• o caminho de um arquivo PNG de entrada, opaco, com dimensões positivas e pixels somente pretos ou brancos;
• o caminho do arquivo PNG de saída;
• uma sequência ordenada com pelo menos duas entradas de cor no formato R,G,B.

Cada componente R, G e B deve ser um inteiro entre 0 e 255. Nenhuma entrada da paleta pode ser preta (0,0,0) nem branca (255,255,255). Entradas iguais na paleta são permitidas, embora produzam camadas visualmente iguais. Para os testes iniciais, o programa deve aceitar imagens de até 128 por 128 pixels.

O formato de execução de referência é:

programa entrada.png saida.png R1,G1,B1 R2,G2,B2 [outras cores]

O apoio de leitura e gravação de imagens indicado na opção 2 também pode ser usado nesta opção.

Regras essenciais

• Preserve todos os pixels pretos e pinte todos os pixels brancos.
• Considere apenas vizinhos por cima, por baixo, pela esquerda e pela direita.
• Use a menor distância dentro da própria região.
• Troque a cor ao avançar de uma camada de distância, não a cada pixel processado.
• Marque cada pixel para impedir inserções repetidas e ciclos de processamento.
• A fila deve ser explícita e encadeada.
• A paleta deve preservar a ordem recebida e repetir as cores circularmente. Ela pode ser representada por um vetor e um índice.
• Cada nova região deve começar na primeira cor da paleta.
• Se o arquivo ou a paleta não cumprir o contrato de entrada, informe o motivo e não produza uma imagem parcial como resultado.

Saída obrigatória

Salve no caminho solicitado uma imagem PNG colorida com as mesmas dimensões da entrada. Informe a quantidade de regiões pintadas e liste uma vez a paleta recebida, na ordem original. Preserve todos os pixels pretos.

O resultado apresenta faixas discretas de cor. Não é necessário suavizar a transição entre as camadas.

Casos para verificar

• Uma região com mais camadas do que cores: confira o retorno à primeira cor e a uniformidade de cada camada.
• Várias regiões separadas: confira a pintura independente e o reinício da paleta.
• Uma região que alcança algum limite da imagem: confira a pintura completa sem acessar posições externas à matriz.

Exemplo visual do módulo e da pintura

A figura mostra uma região branca de 4 por 4 pixels, uma paleta circular com três cores e a correspondência entre distância, resto da divisão e cor. A grade, os números e o contorno são anotações didáticas e não fazem parte da imagem processada.

Limite do projeto

Use imagens binárias preparadas, sem pixels cinza e sem transparência. Não são exigidos reconhecimento de objetos, cores aleatórias, transições suaves ou cores diferentes entre regiões vizinhas.

Opção 4: dispensador automático

Contexto

Um dispensador armazena um único material e possui mecanismos que liberam quantidades fixas desse material. Cada mecanismo pode ser imaginado como um botão: ao ser acionado, ele libera integralmente sua quantidade configurada. Botões diferentes liberam o mesmo material, mas podem liberar quantidades diferentes. O mesmo botão pode ser acionado novamente.

Por exemplo, um dispensador de ração pode possuir três botões que liberam, respectivamente, 1, 3 e 4 gramas. Se o cliente solicitar 6 gramas, o programa deve calcular quantas vezes cada botão será acionado para liberar exatamente o pedido com o menor número total de acionamentos.

O resultado é a quantidade de acionamentos de cada mecanismo, não uma ordem temporal obrigatória. Como todos os acionamentos apenas somam porções do mesmo material, qualquer ordem que preserve essas quantidades produz o mesmo total.

Neste projeto, o dispensador é uma simulação. As quantidades são inteiras e usam uma unidade comum, como gramas. O programa planeja a dosagem, mas não controla equipamentos físicos.

Uma solução é exata quando a soma das quantidades liberadas é igual ao pedido. Entre as soluções exatas, uma solução ótima usa a menor quantidade total de acionamentos.

Objetivo

Implemente um programa que encontre uma solução exata com o menor número total de acionamentos. Use programação dinâmica, por memoização ou tabulação, e reconstrua quantas vezes cada mecanismo participa da solução encontrada.

Modelagem do problema

Considere um pedido de Q unidades do material e M mecanismos disponíveis. O mecanismo de índice i libera d_i unidades por acionamento. Portanto, Q representa a quantidade solicitada, M representa a quantidade de botões e cada d_i representa a porção liberada por um desses botões.

Defina F(q) como o menor número de acionamentos capaz de formar exatamente a quantidade q. O caso base é F(0) = 0. Para uma quantidade positiva, uma candidata pode usar o mecanismo d_i quando q - d_i não for negativo e possuir solução exata:

$$F(q) = \min_{i} \left(1 + F(q - d_i)\right)$$

O mínimo considera somente mecanismos que não ultrapassem q e cujo restante possua solução exata. Quando nenhuma candidata atender a essas condições, marque o estado q como impossível.

O valor zero não pode representar impossibilidade, pois F(0) = 0 é uma resposta válida: formar zero unidades exige zero acionamentos. Uma implementação pode usar -1, um valor especial como INT_MAX ou SIZE_MAX, ou uma estrutura separada que indique se o estado possui solução. Se usar um valor máximo como infinito, verifique a impossibilidade antes de somar 1, para evitar estouro numérico. Na memoização, diferencie também um estado ainda não calculado de um estado já calculado e impossível.

Calcular F(Q) informa somente o menor número de acionamentos. A saída também exige saber quais mecanismos produzem esse custo. Para isso, registre em cada estado possível o índice do mecanismo que gerou a decisão mantida.

Depois do cálculo, faça a reconstrução:

1. comece com a quantidade restante igual a Q;
2. consulte o mecanismo registrado para essa quantidade;
3. aumente em uma unidade a contagem desse mecanismo;
4. subtraia do restante a quantidade liberada por ele;
5. repita até o restante chegar a zero.

No exemplo com pedido 6 e mecanismos 1, 3 e 4, a decisão de F(6) usa o mecanismo de 3 unidades e deixa restante 3. A decisão de F(3) usa novamente esse mecanismo e deixa restante 0. A reconstrução produz, portanto, as contagens 0, 2 e 0, na ordem dos mecanismos da entrada. Se F(Q) for impossível, não inicie a reconstrução. Se houver empate entre combinações mínimas, qualquer uma delas será aceita.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: quantidade solicitada Q e quantidade M de mecanismos;
2. segunda linha: as M quantidades liberadas, na ordem dos mecanismos.

Considere 0 <= Q <= 10000, 1 <= M <= 10 e cada d_i como um inteiro positivo.

6 3
1 3 4

Nesse exemplo, o pedido é de 6 unidades e os mecanismos liberam 1, 3 e 4 unidades. Os valores são configuráveis e não podem ser tratados como constantes do algoritmo.

Considere inválida uma entrada que viole os limites, contenha valor não inteiro ou apresente uma quantidade de mecanismos diferente da quantidade declarada. Informe o motivo e não apresente uma solução parcial.

Regras essenciais

• Cada acionamento libera integralmente a quantidade do mecanismo escolhido. Não existem acionamentos parciais.
• Cada mecanismo pode ser acionado quantas vezes forem necessárias. O estoque de material não limita o modelo.
• A soma liberada deve ser exatamente igual ao pedido. Exceder o pedido ou deixar uma falta não é permitido.
• Cada acionamento possui custo igual a uma unidade, independentemente do mecanismo.
• A solução deve usar programação dinâmica por memoização ou tabulação. Cada estado resolvido deve ser reutilizado, sem recalcular repetidamente o mesmo subproblema.
• Registre, para cada estado possível, uma decisão que permita descobrir qual mecanismo foi usado. Reconstruir uma combinação mínima significa transformar essas decisões nas contagens exibidas na saída. Calcular somente F(Q) não atende ao projeto.
• Escolher repetidamente o maior mecanismo que cabe é uma estratégia gulosa: ela toma a decisão local de maior quantidade sem comparar todos os subproblemas relevantes. Essa estratégia, assim como usar somente divisão inteira ou resto, não garante a solução ótima. O projeto exige programação dinâmica.
• Quando Q = 0, a solução usa zero acionamentos.
• Quando Q for impossível de formar, informe essa condição sem apresentar uma combinação aproximada.

Saída obrigatória

Mostre, na ordem da entrada, quantas vezes cada mecanismo será acionado. Informe também o total de acionamentos e a quantidade total liberada.

Para a entrada de referência, uma saída semanticamente equivalente a esta é esperada:

Mecanismo 1 (1 unidade): 0 acionamentos
Mecanismo 2 (3 unidades): 2 acionamentos
Mecanismo 3 (4 unidades): 0 acionamentos
Total de acionamentos: 2
Quantidade liberada: 6

Outra combinação também será aceita quando possuir soma 6 e usar a mesma quantidade mínima de acionamentos. Quando o pedido for impossível, apresente somente essa condição, sem quantidades aproximadas.

Exemplo visual da programação dinâmica e da reconstrução

A figura usa o pedido 6 e os mecanismos 1, 3 e 4. A escolha local do maior mecanismo produz 4 + 1 + 1, com três acionamentos. A programação dinâmica compara os estados já resolvidos, registra o custo mínimo igual a dois e reconstrói 3 + 3.

Casos para verificar

• Escolha do maior mecanismo não ótima: use Q = 6 e mecanismos 1, 3 e 4. Confira a solução com dois acionamentos do mecanismo de 3 unidades.
• Quantidade impossível: use Q = 7 e mecanismos 4 e 6. Confira que o programa informa a impossibilidade sem apresentar aproximação.
• Pedido zero: use Q = 0 e mecanismos 2, 5 e 9. Confira zero acionamentos para todos os mecanismos e zero unidades liberadas.

Para cada caso, registre a entrada, a saída obtida e uma verificação manual curta. Confirme que a soma reconstruída coincide com o pedido e que a quantidade de acionamentos coincide com o custo mínimo calculado.

Limite do projeto

Trabalhe com um material por execução e quantidades inteiras. Não são exigidos mistura de materiais, estoques limitados, precisão física de dosagem, acionamentos com custos diferentes ou comparação entre memoização e tabulação.

Opção 5: montagem automática de escala

Contexto

Um evento precisa de uma pessoa responsável por cada turno. As pessoas possuem disponibilidades diferentes e um limite individual de participação. Uma escolha permitida para o turno atual pode impedir o preenchimento de um turno seguinte.

Por exemplo, se Ana pode trabalhar de manhã ou à tarde e Bia pode trabalhar somente de manhã, atribuir a manhã a Ana pode deixar a tarde sem responsável. A busca precisa conseguir desfazer essa atribuição e tentar Bia pela manhã.

Esse retorno a uma decisão anterior recebe o nome de backtracking. O programa constrói uma escala parcial, verifica as restrições e retorna quando a escolha atual não permite completar a escala. Uma escala parcial contém apenas os turnos já preenchidos. Ela não é uma resposta completa.

Objetivo

Implemente um programa que encontre uma escala completa válida, usando backtracking com restauração do estado e poda por inviabilidade. A escala deve cobrir todos os turnos informados e respeitar a disponibilidade, o limite total e o limite diário de cada pessoa.

O objetivo é encontrar uma solução que satisfaça as regras. Não é necessário escolher a distribuição mais equilibrada nem listar todas as escalas possíveis.

Modelagem do problema

Considere P pessoas e T turnos. Cada turno possui um dia e um período. Cada pessoa possui um limite total de turnos e uma indicação de disponibilidade para cada turno.

Represente a escala por uma sequência de T atribuições, uma para cada turno na ordem da entrada. Para decidir a próxima atribuição, examine as pessoas disponíveis. Uma candidata pode receber o turno somente quando ainda não atingiu seu limite total e ainda não possui outro turno no mesmo dia.

Mantenha, durante a busca, a pessoa atribuída a cada turno preenchido, a quantidade de turnos de cada pessoa e a informação de quais dias ela já ocupa. Ao aceitar uma candidata, atualize essas informações antes de avançar ao próximo turno.

Se não conseguir completar a escala a partir dessa escolha, desfaça todas as alterações antes de tentar outra pessoa. Remova a atribuição, reduza a contagem individual e libere o dia que essa decisão ocupava. Desfazer somente a atribuição, mantendo a contagem ou o dia ocupado, altera as tentativas seguintes e pode produzir uma conclusão incorreta de impossibilidade.

Uma escolha que já viole uma restrição deve ser descartada sem expandir seus próximos turnos. Esse descarte é uma poda por inviabilidade, pois a atribuição já é inválida. A busca pode encerrar assim que preencher todos os turnos. Se todas as alternativas necessárias forem esgotadas sem uma escala completa, a entrada não possui solução.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: quantidade P de pessoas e quantidade T de turnos;
2. próximas T linhas: dia e período de cada turno;
3. próximas P linhas: identificador da pessoa, limite total e T valores de disponibilidade, na ordem dos turnos.

Considere 1 <= P <= 6 e 1 <= T <= 10. O dia é um inteiro entre 1 e 5. O período é M, para manhã, ou T, para tarde. Cada combinação de dia e período pode aparecer somente uma vez. A disponibilidade usa 1 para disponível e 0 para indisponível. O limite individual é um inteiro maior ou igual a zero. Cada identificador deve possuir de 1 a 31 caracteres, sem espaços, e não pode se repetir.

2 3
1 M
1 T
2 M
Ana 2 1 1 1
Bia 1 1 0 0

No exemplo, Ana está disponível nos três turnos e pode receber até dois. Bia está disponível somente na manhã do dia 1 e pode receber um turno. A disponibilidade autoriza uma tentativa, mas não elimina as demais restrições.

Considere inválida uma entrada que viole as quantidades, os identificadores, os dias, os períodos ou os valores definidos, repita um turno ou forneça uma quantidade de disponibilidades diferente de T. Informe o motivo sem iniciar a busca. Uma entrada válida sem escala possível é diferente de uma entrada inválida.

Regras essenciais

• Cada turno informado deve receber exatamente uma pessoa.
• Uma pessoa pode receber somente turnos em que esteja disponível.
• Uma pessoa pode trabalhar em no máximo um turno por dia, mesmo que esteja disponível nos dois períodos.
• A quantidade de turnos atribuídos a uma pessoa não pode superar seu limite individual.
• Use backtracking com decisões parciais, verificação das restrições e restauração completa do estado ao retornar.
• Descarte candidatas que já violem uma restrição, sem expandir essa atribuição.
• Não conclua impossibilidade somente porque a primeira sequência de escolhas falhou.
• Qualquer escala completa que respeite todas as regras será aceita.
• Todas as pessoas estão aptas ao mesmo trabalho. Não existem qualificações diferentes neste modelo.

Saída obrigatória

Mostre a pessoa atribuída a cada turno, na ordem dos turnos da entrada. Informe também o total de turnos de cada pessoa, na ordem em que as pessoas foram recebidas, incluindo quem não recebeu turno.

Para a entrada de referência, a saída esperada é:

Dia 1, manha: Bia
Dia 1, tarde: Ana
Dia 2, manha: Ana
Total de Ana: 2
Total de Bia: 1

Quando não existir escala válida, informe essa condição sem apresentar atribuições parciais como solução. Em uma execução pequena que exija retorno, apresente também pelo menos uma atribuição desfeita e o estado restaurado antes da nova tentativa. Esse registro pode aparecer no terminal.

Exemplo visual do retorno e da restauração

A figura usa a entrada de referência e uma busca que tenta Ana antes de Bia. A atribuição inicial de Ana à manhã do dia 1 impede preencher a tarde desse dia. Ao retornar, a busca remove a atribuição, devolve a contagem de Ana a zero e libera o dia 1. A nova tentativa usa Bia de manhã e permite completar a escala com Ana nos dois turnos restantes.

Casos para verificar

• Retorno necessário: use a entrada de referência e tente Ana primeiro. Confira o desfazimento da escolha e a escala completa apresentada.
• Disponibilidade sem solução: use um dia com os dois períodos e apenas uma pessoa, disponível nos dois, com limite total 2. Confira a impossibilidade, pois essa pessoa não pode receber dois turnos no mesmo dia.
• Limite individual: use dois turnos em dias diferentes e apenas uma pessoa disponível nos dois, com limite 1. Confira a impossibilidade mesmo sem conflito diário.
• Pessoa com limite zero: acrescente à entrada de referência uma pessoa disponível em todos os turnos, mas com limite 0. Confira que ela recebe zero turnos.
• Entrada inválida: repita a combinação de dia e período de um turno. Confira que o programa informa o erro sem iniciar a busca.

Para cada caso, registre a entrada, a saída obtida e uma verificação manual curta. No caso de retorno, confira a restauração da atribuição, da contagem e da ocupação diária.

Limite do projeto

O núcleo do projeto inclui validar a entrada, construir uma escala por backtracking, podar atribuições inviáveis, restaurar o estado e verificar os casos propostos.

Trabalhe com um evento de até cinco dias. Não são exigidos equilíbrio entre pessoas, preferências, rodízio entre semanas, regras trabalhistas, troca automática de turnos, escolha de uma escala ótima ou listagem de todas as soluções.

Opção 6: seleção de sensores para uma estação remota

Contexto

Uma estação de monitoramento possui energia suficiente para manter somente parte dos sensores disponíveis durante um período. Cada sensor possui um consumo para esse período e uma pontuação de benefício. O programa escolhe quais sensores ativar para obter o maior benefício sem ultrapassar a energia disponível.

Neste projeto, cada sensor é apenas um registro com identificador, consumo e benefício. As unidades são convencionais e os valores já são fornecidos na entrada. Não é necessário pesquisar equipamentos, conhecer eletrônica ou conectar sensores reais.

Cada sensor pode ser escolhido por inteiro ou deixado de fora. Esse modelo é uma mochila 0/1 com energia como capacidade e benefício como valor. Nesta opção, a técnica exigida é branch-and-bound. A opção 12 usa programação dinâmica em outro contexto.

Objetivo

Implemente uma busca por branch-and-bound que encontre uma seleção válida de maior benefício total. Além de rejeitar seleções com consumo excessivo, descarte ramos que não possam melhorar a melhor seleção válida já encontrada.

Encontrar apenas uma seleção que caiba no orçamento não atende ao objetivo. O programa precisa garantir que nenhuma seleção válida possui benefício maior.

Modelagem do problema

Considere um orçamento de energia E e n sensores. O sensor de índice i possui consumo e_i e benefício b_i. Uma seleção pode incluir cada sensor no máximo uma vez. Seu consumo e seu benefício são as somas dos valores dos sensores escolhidos.

Uma seleção é válida quando o consumo total é menor ou igual a E. A seleção vazia é válida, consome zero e possui benefício zero. A energia disponível não precisa ser totalmente utilizada.

Cada nível da busca decide incluir ou excluir um sensor ainda não decidido. Mantenha os sensores selecionados, o consumo acumulado e o benefício acumulado. A melhor seleção válida conhecida é chamada de incumbente. Inicialmente, ela pode ser a seleção vazia.

Há dois motivos diferentes para descartar um ramo:

• excesso de consumo: a seleção parcial já ultrapassa E;
• poda por limite: mesmo uma estimativa otimista do benefício final não supera o benefício do incumbente.

Para maximizar, a estimativa usada na segunda poda é um limite superior. Ela deve ser maior ou igual ao melhor benefício que qualquer continuação daquele ramo conseguiria. Se esse limite for menor ou igual ao benefício do incumbente, o ramo não pode melhorar a resposta e pode ser descartado. A igualdade permite descartar outra solução empatada, pois qualquer seleção ótima é aceita.

Um limite superior pela seleção fracionária

Um limite possível relaxa temporariamente a regra de sensores inteiros. Considere apenas os sensores ainda não decididos, ordenados por benefício dividido pelo consumo, do maior para o menor. Use a energia restante para somar benefícios inteiros enquanto houver espaço. Quando o próximo sensor não couber por inteiro, acrescente somente a fração de seu benefício correspondente à energia restante e encerre esse cálculo.

Some essa contribuição ao benefício já acumulado. Permitir uma fração aumenta as possibilidades consideradas no cálculo do limite. Portanto, o ótimo dessa versão fracionária não é menor que o melhor benefício obtido somente com sensores inteiros. A fração serve apenas para o limite e nunca pode aparecer na seleção final.

Como os benefícios finais são inteiros, o limite fracionário pode ser arredondado para cima antes da comparação. Não use aproximações numéricas que reduzam o limite por erro de cálculo. Outro limite superior seguro também será aceito, desde que a implementação realmente realize poda por limite em pelo menos um caso demonstrado.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: orçamento de energia E e quantidade n de sensores;
2. próximas n linhas: identificador, consumo e benefício de cada sensor.

Considere 0 <= E <= 10000, 1 <= n <= 20, 1 <= e_i <= 10000 e 1 <= b_i <= 1000000. Cada identificador deve possuir de 1 a 31 caracteres, sem espaços, e não pode se repetir.

10 4
A 4 10
B 6 12
C 5 8
D 3 5

Nesse exemplo, selecionar A e B consome 4 + 6 = 10 unidades e fornece benefício 10 + 12 = 22. A seleção é válida. Selecionar também D produziria consumo 13 e violaria o orçamento.

Considere inválida uma entrada que viole os limites, repita identificadores, contenha campo numérico não inteiro ou forneça uma quantidade de sensores diferente da declarada. Informe o motivo sem executar a busca.

Regras essenciais

• Cada sensor pode ser selecionado no máximo uma vez e somente por inteiro.
• Consumos e benefícios são somados, sem dependências ou bônus entre sensores.
• O consumo total não pode ultrapassar o orçamento.
• Use branch-and-bound com decisões de inclusão e exclusão, incumbente e limite superior seguro.
• Rejeitar apenas seleções com consumo excessivo não substitui a poda por limite exigida.
• Atualize o incumbente somente com uma seleção válida que melhore seu benefício.
• Preserve a seleção associada ao incumbente para apresentar os sensores escolhidos ao terminar.
• A ordem de exploração é livre. Se ordenar sensores para calcular o limite ou organizar a busca, preserve seus identificadores e sua posição original para a saída.
• Em empate no benefício ótimo, qualquer seleção empatada será aceita.
• Quando o orçamento for zero ou nenhum sensor couber, a resposta é a seleção vazia com totais zero.

Saída obrigatória

Liste os sensores selecionados na ordem da entrada e informe o consumo total, o benefício total e a energia não utilizada. Mostre separadamente a quantidade de descartes por excesso de consumo e a quantidade de podas por limite.

Para a entrada de referência, a parte referente à seleção deve ser semanticamente equivalente a:

Sensores selecionados: A B
Consumo total: 10
Beneficio total: 22
Energia nao utilizada: 0

As contagens de descarte dependem da ordem da busca e do limite usado. Para tornar o registro verificável, conte cada ramo descartado uma vez. Primeiro verifique excesso de consumo. Em um estado viável ainda com decisões pendentes, verifique a poda por limite. Não conte uma seleção completa somente avaliada como uma poda.

Em uma execução pequena, mostre também pelo menos um ramo descartado por limite, as decisões já fixadas, o benefício do incumbente e o limite usado na comparação. Os valores podem variar entre implementações, mas precisam justificar o descarte.

Exemplo visual do incumbente e da poda

A figura usa a entrada de referência. Depois que A B é conhecido como incumbente de benefício 22, considere o ramo que exclui A. A seleção fracionária dos sensores restantes usa B inteiro, D inteiro e um quinto de C, produzindo limite 12 + 5 + 8/5 = 18,6. Mesmo arredondado para 19, esse limite não supera 22. O ramo inteiro pode ser descartado. A figura mostra esse estado da busca, sem impor uma ordem única de exploração.

Casos para verificar

• Entrada de referência: confira A B, consumo 10 e benefício 22. Compare manualmente os 16 subconjuntos dos quatro sensores.
• Poda por limite: use a referência ou outra entrada pequena. Registre ao menos um ramo descartado por limite e confira que o limite não supera o incumbente.
• Nenhum sensor cabe: use orçamento 2 e sensores A 3 10 e B 4 20. Confira seleção vazia, consumo zero e benefício zero.
• Orçamento zero: use sensores válidos e E = 0. Confira seleção vazia e totais zero.
• Energia não preenchida: use orçamento 6 e sensores A 4 10, B 5 12 e C 6 11. Confira B, benefício 12 e uma unidade de energia livre.
• Entrada inválida: forneça consumo zero ou identificadores repetidos. Confira a indicação do erro sem resultado parcial.

Para cada caso, registre a entrada, a saída obtida e uma verificação manual curta. No caso de poda, diferencie um limite seguro de uma seleção realizável. Um limite pode conter frações, mas a solução não pode.

Limite do projeto

O núcleo do projeto inclui validar a entrada, executar branch-and-bound, manter o incumbente, calcular um limite seguro, reconstruir a seleção armazenada e demonstrar a poda por limite.

Use somente um orçamento de energia. Não são exigidos limites simultâneos de peso ou dinheiro, conexão com sensores reais, programação dinâmica, meta-heurísticas ou comparação de desempenho. Com até 20 sensores, a busca ainda pode examinar muitos ramos, mesmo usando podas.

Opção 7: redução de uma suíte de testes

Contexto

Em software, um requisito descreve um comportamento ou uma condição que o sistema deve atender. Um caso de teste, chamado de teste neste projeto, descreve uma situação usada para verificar um ou mais requisitos. Uma suíte de testes é o conjunto de testes já disponível para verificar o sistema.

A relação entre testes e requisitos pode ocorrer em ambas as direções. Um teste pode cobrir vários requisitos, e um requisito pode ser coberto por vários testes. Quando dois ou mais testes cobrem o mesmo requisito, existe redundância de cobertura.

Suítes grandes podem exigir mais tempo para serem executadas e analisadas. A redução busca selecionar uma parte dos testes existentes que mantenha todos os requisitos cobertos. Neste projeto, os testes são considerados previamente definidos. O programa não decide quais testes devem ser implementados nem executa testes reais. Ele recebe a relação de cobertura e decide quais testes selecionar.

O modelo usa uma simplificação: um valor 1 na matriz informa que o teste fornece a cobertura necessária para considerar aquele requisito coberto. Na prática, essa informação isolada não comprova que o requisito foi completamente validado nem garante a detecção de defeitos.

Objetivo

Implemente duas estratégias para reduzir uma suíte de testes já existente. A estratégia exata por força bruta deve encontrar uma seleção válida com a menor quantidade possível de testes. A estratégia gulosa deve construir uma seleção conforme a regra definida neste enunciado. Compare os resultados obtidos pelas duas estratégias.

O programa processa uma relação de cobertura fornecida na entrada. Não é necessário executar testes de um software real nem medir cobertura de código.

Modelagem do problema

Considere o conjunto de requisitos $R = \{r_1, r_2, \ldots, r_m\}$ e o conjunto de testes $T = \{t_1, t_2, \ldots, t_n\}$. O índice $i$, entre $1$ e $n$, identifica a posição de cada teste no conjunto $T$.

Para cada teste $t_i$, a função $C(t_i)$ indica o subconjunto de requisitos cobertos por esse teste. Por exemplo, $C(t_2) = \{r_1, r_3\}$ significa que o teste $t_2$ cobre os requisitos $r_1$ e $r_3$.

Uma seleção $S \subseteq T$ é válida quando as coberturas dos testes escolhidos, consideradas em conjunto, incluem todos os requisitos:

$$\bigcup_{t_i \in S} C(t_i) = R$$

Em palavras, a expressão afirma que, para cada requisito de $R$, existe pelo menos um teste selecionado em $S$ que o cobre. Como $C(t_i)$ contém somente requisitos pertencentes a $R$, a união é igual a $R$ quando nenhum requisito fica descoberto.

Cada teste possui custo igual a uma unidade. Portanto, o custo de $S$ é sua quantidade de testes, indicada por $|S|$. Uma solução ótima é uma seleção válida com o menor $|S|$ possível, isto é, o menor número de testes que, em conjunto, cobrem todos os requisitos.

Represente a relação de cobertura por uma matriz binária. Cada linha corresponde a um teste, cada coluna corresponde a um requisito, 1 significa que o teste cobre o requisito e 0 significa que não cobre.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: quantidade n de testes e quantidade m de requisitos;
2. segunda linha: os m identificadores dos requisitos, na ordem das colunas;
3. próximas n linhas: identificador do teste seguido por m valores binários.

Considere de 1 a 15 testes e de 1 a 20 requisitos. Identificadores não podem conter espaços nem se repetir dentro do próprio conjunto.

4 5
R1 R2 R3 R4 R5
T1 1 1 0 0 0
T2 0 0 1 1 0
T3 0 0 0 0 1
T4 1 0 1 0 1

Nesse exemplo, T1 cobre R1 e R2, enquanto T4 cobre R1, R3 e R5. A matriz fornece toda a informação necessária sobre abrangência. O programa não precisa descobrir o que cada teste cobre.

Exemplo visual de seleções candidatas

A figura compara três seleções para a matriz de referência. A primeira cobre todos os requisitos, mas usa um teste desnecessário. A segunda deixa R4 descoberto e, por isso, é inválida. A terceira cobre todos os requisitos com três testes e é ótima, pois nenhuma seleção com apenas dois testes cobre as cinco colunas. A figura não associa as seleções às estratégias e não antecipa uma conclusão geral sobre a estratégia gulosa.

Regras essenciais

• Um requisito está coberto quando pelo menos um teste selecionado possui 1 na coluna correspondente.
• Cobrir o mesmo requisito várias vezes não reduz o custo nem fornece benefício adicional.
• Cada teste pode ser selecionado no máximo uma vez.
• A força bruta deve examinar os subconjuntos de testes e garantir uma solução com quantidade mínima quando a cobertura completa for possível.
• A estratégia gulosa deve escolher, a cada passo, o teste que cobre a maior quantidade de requisitos ainda não cobertos.
• A contribuição gulosa deve ser recalculada depois de cada escolha.
• Em empate na estratégia gulosa, escolha o primeiro teste na ordem da entrada.
• Antes de executar as estratégias, verifique se cada requisito aparece em pelo menos um teste. Quando uma coluna possui somente zeros, a cobertura completa é impossível.
• Em empate entre soluções exatas mínimas, qualquer uma será aceita.
• Se a entrada violar quantidades, identificadores ou valores definidos no contrato, informe o motivo e não execute as estratégias.

Saída obrigatória

Mostre, separadamente, os testes escolhidos e a quantidade usada por cada estratégia. Na solução exata, apresente os identificadores na ordem em que aparecem na entrada. Na solução gulosa, apresente os identificadores na ordem em que foram escolhidos. Compare a quantidade da seleção gulosa com a quantidade mínima encontrada por força bruta. Se houver diferença, informe quantos testes adicionais foram selecionados.

Para a entrada de referência, uma saída semanticamente equivalente a esta é esperada:

Forca bruta: 3 testes, T1 T2 T3
Guloso: 3 testes, T4 T1 T2
Quantidade do guloso igual ao minimo: sim
Testes adicionais: 0

Se a cobertura completa for impossível, não execute as duas estratégias. Liste, na ordem da entrada, todos os requisitos que não aparecem em teste algum. Não mostre nem classifique uma seleção parcial como solução.

Análise obrigatória

Determine se a regra gulosa definida neste enunciado sempre garante uma seleção com quantidade mínima. Justifique a conclusão com uma demonstração válida ou com uma entrada que funcione como contraexemplo. Se usar um contraexemplo, apresente a matriz e as saídas das duas estratégias. Uma única entrada em que as quantidades coincidem não demonstra o comportamento para todas as entradas possíveis.

Casos para verificar

Além da entrada de referência, crie e execute no mínimo três entradas próprias:

• uma suíte com sobreposição e redundância entre as coberturas;
• uma suíte com pelo menos um requisito impossível de cobrir;
• um caso-limite válido, como uma suíte com um teste e um requisito.

Para cada entrada criada, registre a entrada, a saída obtida e uma verificação manual curta dos requisitos cobertos pela seleção. Compare o resultado esperado antes da execução com o resultado produzido pelo programa. Crie outras entradas quando forem necessárias para sustentar a análise obrigatória.

Limite do projeto

O núcleo do projeto inclui ler e validar a matriz, executar as duas estratégias, comparar os resultados e verificar o programa com entradas criadas pelo grupo. Use somente a matriz como fonte da relação de cobertura.

Não são exigidos análise do código-fonte de outro software, implementação ou execução de testes reais, medição automática de cobertura, prioridades, custos diferentes entre testes ou garantia de detecção de defeitos. Os casos criados pelo grupo podem ser arquivos de texto simples. Não é necessário implementar um framework de testes automatizados.

Opção 8: substituição em cache com acessos conhecidos

Contexto

Uma memória cache é um armazenamento pequeno e de acesso rápido que mantém cópias de itens usados pelo sistema. Quando um item solicitado já está na cache, o acesso pode ser atendido sem buscar novamente esse item em um armazenamento mais lento.

Neste projeto, a cache é apenas uma simulação. Ela possui c posições, também chamadas de espaços. Cada item ocupa exatamente uma posição, independentemente de seu identificador. Carregar um item significa colocar uma cópia dele em uma posição da cache. Remover um item apaga somente essa cópia simulada. O item continua disponível fora da cache e pode ser carregado novamente em um acesso posterior.

Um acesso é uma solicitação por um item. O acesso produz um acerto quando o item já está na cache e uma falta quando ele não está. Em um sistema real, uma falta tende a exigir uma busca mais lenta. O modelo representa esse trabalho atribuindo custo de uma unidade a cada falta e custo zero a cada acerto. Portanto, minimizar as faltas representa reduzir as buscas no armazenamento mais lento.

Uma política de substituição define qual item deve ser removido quando ocorre uma falta e todas as posições da cache já estão ocupadas. As duas políticas comparadas neste projeto são a ótima offline e a FIFO. A sigla FIFO significa first in, first out, ou primeiro a entrar, primeiro a sair.

Objetivo

Implemente duas simulações independentes para a mesma sequência de acessos. A primeira deve usar a política ótima offline, baseada em uma estratégia gulosa. A segunda deve usar a política FIFO, implementada com uma fila encadeada. Compare as quantidades de acertos e faltas.

No modelo offline, a sequência completa de acessos é conhecida antes do início da simulação. Por isso, a política ótima offline pode consultar os acessos futuros ao escolher um item para remoção. Essa possibilidade serve como referência teórica e não representa uma cache real capaz de prever o futuro.

Modelagem do problema

Considere a sequência $A = (a_1, a_2, \ldots, a_n)$, formada por n acessos, e uma cache com capacidade c. O símbolo $a_i$ identifica o item solicitado no acesso de índice $i$, entre 1 e n. Um mesmo identificador pode aparecer várias vezes na sequência.

Antes do primeiro acesso, a cache está vazia. Ao processar $a_i$:

• ocorre um acerto quando $a_i$ já está na cache. O estado permanece inalterado;
• ocorre uma falta quando $a_i$ não está na cache. Uma cópia de $a_i$ deve ser carregada;
• quando existe uma posição livre, $a_i$ entra nessa posição sem remover outro item;
• quando as c posições estão ocupadas, a política escolhe um item para remoção antes da entrada de $a_i$.

Depois de cada acesso, o item solicitado deve estar na cache. As políticas ótima offline e FIFO devem receber a mesma sequência, mas cada simulação começa novamente com a cache vazia. Os estados das duas simulações são independentes.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: capacidade c e quantidade n de acessos;
2. segunda linha: os n identificadores inteiros, na ordem dos acessos.

Considere 1 <= c <= 5 e 10 <= n <= 30.

3 12
1 2 3 4 1 2 5 1 2 3 4 5

Considere inválida uma entrada cuja capacidade ou quantidade de acessos esteja fora dos limites, que contenha um valor não inteiro ou cuja segunda linha não possua exatamente n identificadores. Por exemplo, declarar n = 12 e fornecer somente 11 identificadores viola o contrato. Informe o motivo e não inicie nenhuma simulação.

Regras essenciais

Política ótima offline. Em uma falta com a cache cheia, consulte somente o trecho da sequência posterior ao acesso atual:

1. se algum item da cache não aparecer novamente, remova um desses itens;
2. se todos reaparecerem, remova aquele cujo próximo acesso estiver mais distante no futuro.

Essa regra é uma estratégia gulosa porque toma, em cada substituição, a decisão que preserva por mais tempo os itens que serão necessários primeiro. Nas condições do modelo offline, ela produz a menor quantidade possível de faltas. Não é necessário demonstrar formalmente essa propriedade.

Represente essa cache por c posições lógicas numeradas de 0 a c - 1. Um item novo ocupa a posição livre de menor índice. Quando vários itens armazenados não aparecerem novamente, remova aquele que estiver na posição lógica de menor índice. O item solicitado ocupa a mesma posição do item removido. Essas regras de desempate tornam o traço reproduzível.

Política FIFO. Mantenha os itens em uma fila encadeada, do item armazenado há mais tempo para o item armazenado há menos tempo. Em uma falta:

• se existir espaço livre, insira o item solicitado no final da fila sem remover outro item;
• se a cache estiver cheia, remova o item da frente e insira no final o item que produziu a falta.

O item removido deixa de fazer parte da cache e não assume outro papel na simulação. Se ele for solicitado novamente, ocorrerá uma nova falta. Um acerto não move o item nem altera sua posição na fila.

Em ambas as políticas:

• cada acesso deve ser classificado uma única vez como acerto ou falta, portanto a soma do total de acertos + total de faltas deve ser igual a n;
• um acerto não cria outra cópia do item;
• a quantidade de itens nunca pode superar c;
• o item solicitado deve estar na cache depois de cada acesso;
• uma remoção ocorre somente quando existe uma falta e a cache já contém c itens;
• identificadores podem se repetir na sequência, mas a cache não pode conter duas cópias do mesmo item;
• entradas inválidas devem produzir somente uma mensagem com o motivo do erro.

A fila encadeada é obrigatória na política FIFO. A representação da cache ótima pode usar as posições lógicas descritas acima.

Saída obrigatória

Mostre os totais de acertos e faltas de cada política. Para sequências com até 15 acessos, mostre também, depois de cada acesso, o item solicitado, se ocorreu acerto ou falta, o item removido quando houver remoção e o estado resultante da cache. Mostre a cache ótima pela ordem crescente das posições lógicas. Mostre a FIFO do item mais antigo para o mais recente. Para sequências maiores, somente os totais são obrigatórios.

Para a entrada de referência, uma saída resumida semanticamente equivalente a esta é esperada:

Otima offline: 5 acertos, 7 faltas
FIFO: 3 acertos, 9 faltas

Exemplo visual do traço das duas políticas

A figura mostra os 12 acessos da entrada de referência. Na cache ótima offline, o estado apresenta as posições lógicas 0, 1 e 2. Na FIFO, o estado apresenta os itens do mais antigo para o mais recente. O símbolo - indica que nenhum item foi removido, e o símbolo · indica uma posição ainda vazia.

Casos para verificar

Os casos abaixo são verificações obrigatórias do programa. A entrada de referência já verifica uma sequência em que a política ótima offline produz menos faltas que a FIFO. Além dela, crie e execute no mínimo três entradas próprias:

• Capacidade suficiente: use no máximo c identificadores distintos e repita os acessos até alcançar o mínimo de 10. Confira que somente a primeira ocorrência de cada identificador produz falta e que nenhuma remoção ocorre. Esse caso artificial verifica o comportamento quando a cache nunca fica sem espaço para um item novo.
• Um único item: use c = 1 e repita o mesmo identificador pelo menos 10 vezes. Confira uma falta inicial seguida somente por acertos. Esse caso verifica que um acerto não cria duplicatas, não remove o item e não altera o estado.
• Entrada inválida: crie uma entrada que viole uma das quantidades declaradas. Confira que o programa informa o motivo e não apresenta resultados parciais de nenhuma política.

Para cada entrada criada, registre a entrada, a saída obtida e uma verificação manual curta do estado esperado. Compare essa previsão com o resultado produzido pelo programa.

Limite do projeto

O núcleo do projeto inclui ler e validar a sequência, simular separadamente as duas políticas, manter a fila encadeada da FIFO, produzir os traços exigidos e verificar o programa com entradas criadas pelo grupo.

O modelo contém uma única cache inicialmente vazia por política. Não se exigem cache física, medição de tempo real, itens de tamanhos diferentes, operações de escrita, vários níveis de memória, previsão de acessos, processamento online ou otimizações para entradas grandes.

Opção 9: equivalência de regras booleanas

Contexto

Uma regra booleana combina condições que podem assumir somente os valores falso, representado por 0, e verdadeiro, representado por 1. O resultado da regra também é 0 ou 1. Regras desse tipo podem representar, por exemplo, critérios de acesso, filtros ou condições de decisão de um programa.

Duas regras são equivalentes quando produzem o mesmo resultado para toda atribuição possível de valores às suas variáveis. Em uma tabela verdade completa, isso significa que as colunas de resultado das duas regras são iguais em todas as linhas. As expressões podem ter textos diferentes e ainda serem equivalentes.

Verificar equivalência permite confirmar que uma regra reescrita preserva o comportamento da original. Uma única atribuição com resultados diferentes comprova que as regras não são equivalentes. Essa atribuição recebe o nome de contraexemplo. Para confirmar a equivalência, todas as atribuições precisam produzir resultados iguais.

Objetivo

Implemente um programa que verifique se duas regras booleanas são equivalentes. Use força bruta para gerar todas as atribuições possíveis das variáveis. Para cada atribuição, use uma pilha encadeada para calcular separadamente o resultado de cada expressão.

Essas operações cumprem funções diferentes. A força bruta determina quais valores serão atribuídos às variáveis em cada tentativa. A pilha processa os tokens de uma expressão e calcula um único resultado para a atribuição atual. Depois das duas avaliações, o programa compara os resultados.

Quando as regras não forem equivalentes, apresente uma combinação de valores que comprove a diferença.

Modelagem do problema

Cada variável representa uma condição falsa, indicada por 0, ou verdadeira, indicada por 1. Uma atribuição associa exatamente um desses valores a cada variável declarada. Com n variáveis, existem $2^n$ atribuições possíveis.

Cada expressão é formada por tokens, isto é, unidades separadas por espaços. Em A B AND, os tokens são A, B e AND. Os tokens permitidos são:

• variáveis declaradas por letras maiúsculas de A a Z;
• constantes booleanas 0 e 1, que mantêm seus valores em todas as atribuições;
• operador unário NOT;
• operadores binários AND e OR.

Variáveis e constantes são operandos, pois fornecem valores. NOT, AND e OR são operadores, pois transformam esses valores.

A entrada usa notação pós-fixa, na qual o operador aparece depois de seus operandos. Por exemplo, a expressão usual (A AND B) OR (NOT A) é escrita como A B AND A NOT OR. A notação pós-fixa não é universalmente melhor que a notação usual. Ela foi escolhida porque determina a ordem das operações sem parênteses ou regras de precedência e permite uma avaliação direta com pilha.

Avalie cada expressão da esquerda para a direita e inicie cada avaliação com uma pilha vazia:

• ao encontrar uma variável, consulte o valor dela na atribuição atual e empilhe esse valor, não a letra;
• ao encontrar 0 ou 1, empilhe diretamente o valor da constante;
• ao encontrar NOT, desempilhe um valor, negue esse valor e empilhe o resultado;
• ao encontrar AND ou OR, desempilhe o operando da direita e depois o da esquerda, aplique o operador e empilhe o resultado.

Uma expressão válida termina com exatamente um valor na pilha. Esse valor é o resultado da expressão para a atribuição atual.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: quantidade n de variáveis, entre 0 e 10;
2. segunda linha: n variáveis distintas separadas por espaços;
3. terceira linha: primeira expressão pós-fixa;
4. quarta linha: segunda expressão pós-fixa.

Cada expressão pode conter até 50 tokens, contados pelas unidades separadas por espaços. Por exemplo, A B AND possui três tokens.

Quando n for zero, represente a lista vazia de variáveis por uma linha vazia ou por -. Nesse caso, existe $2^0 = 1$ atribuição, a atribuição vazia, e as expressões podem usar somente as constantes 0 e 1 e os operadores permitidos.

2
A B
A B AND
A B OR

Regras essenciais

• Use a mesma atribuição nas duas expressões durante cada comparação. Se A = 1 na atribuição atual, toda ocorrência de A nas duas expressões fornece o valor 1.
• Dentro de uma atribuição, todas as ocorrências da mesma variável possuem o mesmo valor.
• Inicie cada avaliação com uma pilha vazia. As duas expressões não podem compartilhar nós nem valores residuais de pilha.
• A força bruta pode encerrar na primeira divergência encontrada.
• Declare equivalência somente depois de avaliar as duas expressões em todas as $2^n$ atribuições sem encontrar resultados diferentes.
• A pilha usada na avaliação deve ser explícita e encadeada.
• Uma entrada inválida deve ser informada como erro, não como regras não equivalentes.
• Qualquer atribuição divergente será aceita como contraexemplo.

Considere inválida uma expressão vazia, com mais de 50 tokens, com token desconhecido, com variável não declarada, com operador sem valores suficientes ou que deixe mais de um valor na pilha. Considere também inválida uma entrada cuja quantidade de variáveis esteja fora do limite, não corresponda à lista ou contenha variável repetida ou fora do intervalo de A a Z.

Saída obrigatória

Informe se as expressões são equivalentes. Quando não forem, mostre os valores de todas as variáveis no contraexemplo e o resultado de cada expressão para essa atribuição. Quando n = 0, não existe variável para listar.

Para a entrada de referência, uma saída válida é:

Nao equivalentes
A=1 B=0
Expressao 1: 0
Expressao 2: 1

Outra atribuição também será aceita se realmente produzir resultados diferentes. Para uma entrada inválida, informe o motivo sem apresentar uma conclusão de equivalência.

Exemplo visual da pilha e de um contraexemplo

A figura possui dois exemplos independentes. À esquerda, ela avalia A B AND A NOT OR para A = 1 e B = 0, mostrando que a pilha armazena valores booleanos e termina com um único resultado. À direita, ela compara A B AND com A B OR e destaca uma atribuição que produz resultados diferentes. O topo da pilha aparece à direita de cada estado. A tabela verdade completa possui finalidade didática; o programa pode encerrar na primeira divergência encontrada.

Casos de teste fornecidos

Execute todos os casos abaixo. Eles fornecem entradas e resultados esperados para verificar comportamentos diferentes do programa.

Caso 1: divergência com contraexemplo

Use a entrada de referência apresentada anteriormente. A saída deve informar que as expressões não são equivalentes, mostrar uma atribuição divergente e apresentar os dois resultados. A = 1 e B = 0 é um contraexemplo válido, mas não é o único.

Caso 2: textos diferentes e regras equivalentes

2
A B
A B AND
B A AND

Saída esperada:

Equivalentes

Caso 3: uso de NOT em regras equivalentes

2
A B
A B AND A NOT OR
A NOT B OR

Saída esperada:

Equivalentes

Caso 4: expressões constantes sem variáveis

0
-
1 0 OR
1

Saída esperada:

Equivalentes

Caso 5: variável não declarada

1
A
A B AND
A

Saída semanticamente esperada:

Entrada invalida: uma expressao usa uma variavel nao declarada

Neste último caso, não informe equivalência nem apresente contraexemplo.

Limite do projeto

O núcleo do projeto inclui validar a entrada, gerar as atribuições por força bruta, avaliar cada expressão com uma pilha encadeada independente, comparar os resultados e executar os casos de teste fornecidos.

Use somente os operadores e a notação pós-fixa definidos acima. Não se exigem conversão de expressões usuais para pós-fixas, parênteses na entrada, regras de precedência, simplificação algébrica, impressão da tabela verdade completa, circuitos eletrônicos ou métodos avançados de verificação lógica.

Opção 10: circuito mínimo de visita

Contexto

Uma equipe de inspeção parte de uma base, visita alguns pontos e retorna à base. A distância de deslocamento entre cada par de pontos já é conhecida. Mudar a ordem das visitas pode alterar a distância total, mesmo quando todos os pontos são visitados.

Um circuito é a sequência que começa na base, visita cada outro ponto exatamente uma vez e termina novamente na base. A volta final faz parte da distância total. Encontrar o circuito mínimo significa comparar ordens possíveis e garantir que nenhuma delas possui distância menor.

Neste projeto, a matriz de distâncias descreve todo o deslocamento permitido. Não é necessário encontrar caminhos entre pontos em um mapa nem usar coordenadas geográficas.

Objetivo

Implemente uma busca por branch-and-bound que encontre um circuito de menor distância total. Use um limite inferior seguro para descartar rotas parciais que não possam melhorar o melhor circuito completo já encontrado.

Modelagem do problema

Considere n pontos numerados de 0 a n - 1. O ponto 0 é a base. A matriz d[a][b] informa a distância do ponto a até o ponto b. As distâncias são simétricas, isto é, d[a][b] = d[b][a], e todos os pares distintos permitem deslocamento direto.

Uma rota completa possui a forma 0, p_1, p_2, ..., p_(n-1), 0, em que os pontos intermediários são uma permutação de 1 a n - 1. Uma permutação contém todos esses pontos, cada um exatamente uma vez, em alguma ordem. A distância é a soma dos valores da matriz entre posições consecutivas da rota, incluindo a última volta a 0.

Cada nível da busca acrescenta um ponto ainda não visitado. Mantenha a rota parcial, os pontos usados e o custo já percorrido g. Ao retornar de uma tentativa, remova o ponto acrescentado e restaure sua condição de não visitado antes de testar outra continuação.

O incumbente é o circuito completo de menor distância conhecido. Inicialmente, use uma indicação de ausência de circuito ou um circuito completo válido. Não use uma rota incompleta como incumbente. Ao completar uma ordem, some o retorno à base antes de comparar seu custo com o melhor conhecido.

Um limite inferior pelas menores saídas

Seja u o último ponto da rota parcial e U o conjunto dos pontos ainda não visitados. Para cada ponto v, defina m(v) como a menor distância de saída para outro ponto da matriz, excluindo somente o próprio v. Quando U não estiver vazio, use:

$LB = g + \min_{v \in U} d[u][v] + \sum_{v \in U} m(v)$

O símbolo LB representa o limite inferior. O primeiro termo é o custo já percorrido. O segundo é a menor distância possível para sair do ponto atual em direção a um ponto pendente. O último soma uma saída mínima de cada ponto pendente, pois cada um precisará ser deixado depois de ser visitado, inclusive para o retorno final.

As saídas usadas no cálculo podem apontar para pontos já visitados ou formar movimentos incompatíveis entre si. Isso não representa uma rota completa. O cálculo permite essas escolhas porque elas tornam o valor otimista: uma continuação real precisa pagar pelo menos esses mínimos. Portanto, o limite não supera o custo de nenhuma continuação real.

Se não restar ponto em U, use o custo exato g + d[u][0]. Se existir incumbente e LB for maior ou igual ao custo dele, a rota parcial não pode melhorar a resposta e pode ser podada. Outro limite inferior seguro também será aceito, desde que a poda por limite seja efetivamente demonstrada.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: quantidade n de pontos, incluindo a base;
2. próximas n linhas: os n valores de cada linha da matriz, na ordem dos pontos.

Considere 2 <= n <= 8 e distâncias inteiras entre 0 e 1000000. A diagonal deve conter somente zeros e a matriz deve ser simétrica. Distância zero entre pontos distintos é permitida. Não é exigida a desigualdade triangular, isto é, passar por um terceiro ponto não precisa custar mais que o deslocamento direto.

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

O valor 25 na linha do ponto 1 e coluna do ponto 3 representa a distância entre esses pontos. Os valores da matriz são a fonte do custo. O posicionamento dos pontos em uma figura serve apenas para ilustrar a ordem.

Considere inválida uma entrada fora dos limites, com valores não inteiros, matriz de dimensões diferentes das declaradas, distância negativa, diagonal diferente de zero ou valores assimétricos. Informe o motivo sem executar a busca.

Regras essenciais

• Comece e termine no ponto 0.
• Visite cada outro ponto exatamente uma vez e não retorne à base entre as visitas.
• Some todos os deslocamentos da rota, inclusive a volta final.
• Use branch-and-bound com expansão de rotas parciais, incumbente completo e limite inferior seguro.
• Restaure a rota e os pontos visitados ao retornar de uma tentativa.
• Não descarte um ramo por uma estimativa que possa superar o custo de uma continuação válida.
• A ordem de exploração é livre. Em empate, qualquer circuito mínimo será aceito, inclusive o circuito de ordem inversa.
• A matriz permanece fixa durante a busca.

Saída obrigatória

Mostre o circuito completo e a distância total. Para a entrada de referência, uma saída válida é:

Circuito: 0 1 3 2 0
Distancia total: 80

O custo é 10 + 25 + 30 + 15 = 80. O circuito inverso 0 2 3 1 0 também é ótimo. Em uma execução pequena, registre pelo menos uma rota parcial podada, seu custo acumulado, os pontos pendentes, o limite calculado e o custo do incumbente usado na comparação.

Exemplo visual do circuito e da poda

A figura apresenta a matriz de referência e um circuito ótimo. Depois que o custo 80 é conhecido, a rota parcial 0 2 1 já custa 15 + 35 = 50 e deixa somente o ponto 3 pendente. Sua menor saída do ponto 1 para o ponto pendente custa 25, e a menor saída do ponto 3 custa 20. O limite é 50 + 25 + 20 = 95, que não melhora o incumbente 80. O desenho não representa uma escala de distâncias.

Casos para verificar

• Entrada de referência: compare as seis ordens dos pontos 1, 2 e 3. Confira o mínimo 80 e a inclusão do retorno à base.
• Poda por limite: use a referência ou outra entrada pequena. Mostre uma rota parcial, o limite e o incumbente que justificam seu descarte.
• Dois pontos: use a matriz com linhas 0 7 e 7 0. Confira o circuito 0 1 0 e a distância 14.
• Distâncias zero: use três pontos e uma matriz formada somente por zeros. Confira um circuito completo válido com distância zero.
• Entrada inválida: altere apenas um dos dois valores de um par simétrico. Confira que a assimetria é informada antes da busca.

Para cada caso, registre a entrada, a saída obtida e uma verificação manual curta. Recalcule o custo pela matriz e confira que nenhum ponto intermediário falta ou se repete. Ao verificar a poda, lembre que o limite não precisa corresponder a um circuito realizável.

Limite do projeto

O núcleo do projeto inclui validar a matriz, buscar um circuito mínimo, manter um incumbente completo, calcular um limite seguro e demonstrar uma poda.

Use um único circuito e a matriz fornecida. Não são exigidos mapas geográficos, vários veículos, capacidade de carga, horários, obstáculos, caminhos mínimos entre pares ou bibliotecas de grafos. A quantidade de ordens pode crescer como o fatorial de n - 1, mesmo com podas. Por isso, respeite o limite de oito pontos.

Opção 11: sequenciamento com penalidade de atraso

Contexto

Uma máquina precisa executar vários pedidos. Cada pedido possui uma duração, um prazo de conclusão e uma penalidade por unidade de tempo de atraso. Alterar a ordem muda quando cada pedido termina e pode mudar a penalidade total.

O prazo é o instante máximo de conclusão sem penalidade. O atraso é quanto a conclusão ultrapassa esse prazo. Terminar antes do prazo não produz atraso negativo nem desconto na penalidade dos outros pedidos.

Neste projeto, todos os pedidos já estão disponíveis no instante zero. A máquina executa um pedido por vez, até terminar, e começa o próximo imediatamente. O programa decide a ordem em uma simulação, sem controlar uma máquina real.

Objetivo

Implemente uma busca por branch-and-bound que encontre uma ordem com a menor soma das penalidades por atraso. Use um limite inferior seguro para descartar ordens parciais que não possam melhorar a melhor ordem completa já encontrada.

O objetivo considera a soma das penalidades. Escolher sempre o pedido mais curto ou o de menor prazo, sem a busca exigida, não garante essa soma mínima.

Modelagem do problema

Considere n pedidos. O pedido de índice i possui duração p_i, prazo de conclusão d_i e penalidade w_i por unidade de atraso. Durações e prazos usam a mesma unidade de tempo, contada a partir de zero.

Uma ordem válida é uma permutação dos pedidos, contendo cada um exatamente uma vez. O instante de conclusão C_i de um pedido é a soma das durações de todos os pedidos executados até ele, incluindo sua própria duração. Calcule seu atraso T_i e sua penalidade P_i por:

$T_i = \max(0, C_i - d_i)$

$P_i = w_i T_i$

O máximo com zero faz o atraso ser zero quando o pedido termina antes do prazo ou exatamente nele. A penalidade total é a soma de P_i para todos os pedidos. A pontuação w_i é uma taxa fornecida na entrada. Ela não altera a duração do pedido.

Cada nível da busca escolhe o próximo pedido ainda não usado. Mantenha a ordem parcial, o tempo já ocupado t e a penalidade acumulada P. Ao acrescentar um pedido, sua conclusão será t + p_i. Some a penalidade desse pedido e avance com o novo tempo. Ao retornar, restaure a ordem, a disponibilidade do pedido, o tempo e a penalidade anteriores.

O incumbente é a ordem completa válida de menor penalidade conhecida. Inicialmente, use uma indicação de ausência de solução ou uma ordem completa já avaliada. Preserve também os pedidos dessa ordem para apresentar a resposta ao terminar.

Um limite inferior com inícios simultâneos

Seja U o conjunto dos pedidos ainda não escolhidos. Imagine, apenas para calcular o limite, que cada pedido de U pudesse começar imediatamente no tempo atual t. Use:

$LB = P + \sum_{i \in U} w_i \max(0, t + p_i - d_i)$

O símbolo LB representa o limite inferior. A primeira parcela é a penalidade dos pedidos já fixados. A soma estima a penalidade dos restantes, permitindo que todos comecem ao mesmo tempo. Essa execução simultânea não é permitida na resposta, mas torna a estimativa otimista.

Na máquina real, nenhum pedido restante pode começar antes de t. Portanto, nenhum pode terminar antes de t + p_i. Como o atraso e a penalidade não diminuem quando a conclusão aumenta, o limite não supera a penalidade de nenhuma continuação real.

Quando existir incumbente e LB for maior ou igual à penalidade dele, a ordem parcial pode ser podada, pois não consegue melhorar a resposta. A igualdade permite descartar outra solução empatada. Quando não houver pedido restante, o limite coincide com a penalidade exata da ordem completa. Outro limite inferior seguro também será aceito, desde que a poda seja demonstrada.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: quantidade n de pedidos;
2. próximas n linhas: identificador, duração, prazo e penalidade por unidade de atraso.

Considere 1 <= n <= 8, 1 <= p_i <= 10000, 0 <= d_i <= 100000 e 1 <= w_i <= 10000. Cada identificador deve possuir de 1 a 31 caracteres, sem espaços, e não pode se repetir. Escolha um tipo numérico capaz de armazenar as somas e os produtos para todos esses limites.

3
A 3 4 1
B 2 2 5
C 1 3 2

O pedido B dura duas unidades, deve terminar até o instante 2 para não atrasar e custa cinco unidades de penalidade por unidade de atraso. Se terminar no instante 5, seu atraso será 3 e sua penalidade será 15.

Considere inválida uma entrada que viole os limites, repita identificadores, contenha campo numérico não inteiro ou forneça uma quantidade de pedidos diferente da declarada. Informe o motivo sem executar a busca.

Regras essenciais

• Execute todos os pedidos exatamente uma vez.
• Comece o primeiro no instante zero e o próximo quando o anterior terminar.
• Execute um pedido por vez, sem pausas nem interrupções.
• Calcule o atraso com mínimo zero. Antecipação não gera penalidade negativa.
• Minimize a soma das penalidades, sem substituir o objetivo pela soma dos atrasos ou pelo maior atraso individual.
• Use branch-and-bound com ordens parciais, incumbente completo e limite inferior seguro.
• Restaure todo o estado ao retornar de uma tentativa.
• A ordem de exploração é livre. Qualquer ordem ótima será aceita em caso de empate.
• Não use uma execução simultânea como resposta. A simultaneidade aparece somente no limite explicado acima.

Saída obrigatória

Mostre a ordem escolhida. Para cada pedido nessa ordem, informe o instante de conclusão, o atraso e a penalidade. Informe também a penalidade total.

Para a entrada de referência, a saída esperada é:

Ordem: B C A
Pedido B: conclusao 2, atraso 0, penalidade 0
Pedido C: conclusao 3, atraso 0, penalidade 0
Pedido A: conclusao 6, atraso 2, penalidade 2
Penalidade total: 2

Em uma execução pequena, registre pelo menos uma ordem parcial podada, o tempo atual, a penalidade acumulada, os pedidos restantes, o limite calculado e a penalidade do incumbente usado na comparação.

Exemplo visual da execução e da poda

A figura usa a entrada de referência. Na ordem ótima B C A, somente A atrasa, produzindo penalidade total 2. Depois que esse incumbente é conhecido, considere uma ordem parcial que começa por A. O tempo atual é 3 e a penalidade acumulada é zero. Se B e C começassem simultaneamente nesse instante, suas penalidades seriam 15 e 2. O limite é 17, maior que o incumbente 2, permitindo descartar todo o ramo que começa por A. A figura apresenta essa comparação sem impor uma ordem de exploração à busca.

Casos para verificar

• Entrada de referência: compare as seis ordens dos três pedidos. Confira que B C A produz a menor penalidade, igual a 2.
• Poda por limite: use a referência ou outra entrada pequena. Mostre a ordem parcial, as parcelas do limite e o incumbente que justificam o descarte.
• Prazos folgados: use A 3 10 2 e B 2 10 5. Confira penalidade total zero, sem valores negativos, em qualquer ordem.
• Um pedido com prazo zero: use A 3 0 4. Confira conclusão 3, atraso 3 e penalidade total 12.
• Conclusão no prazo: use um único pedido A 3 3 4. Confira conclusão 3, atraso zero e penalidade zero.
• Entrada inválida: forneça duração zero ou penalidade por unidade igual a zero. Confira o erro sem resultado parcial.

Para cada caso, registre a entrada, a saída obtida e uma verificação manual curta. Recalcule as conclusões pela soma das durações e confira cada multiplicação de atraso pela penalidade por unidade. No caso de poda, confira que a estimativa otimista não foi apresentada como execução válida.

Limite do projeto

O núcleo do projeto inclui validar os pedidos, executar branch-and-bound, calcular atrasos e penalidades, preservar a melhor ordem completa e demonstrar a poda por limite.

Use uma única máquina e pedidos disponíveis no instante zero. Não são exigidos instantes de chegada diferentes, pausas, dependências entre pedidos, preparação da máquina, várias máquinas ou otimização do maior atraso. A busca ainda pode crescer de forma fatorial mesmo com podas, por isso respeite o limite de oito pedidos.

Opção 12: seleção de equipamentos para uma expedição

Contexto

Uma equipe precisa transportar equipamentos em uma mochila com capacidade de carga limitada. Cada equipamento possui um peso inteiro e um valor inteiro que representa sua importância para a expedição. Um item pode ser levado por inteiro ou deixado de fora.

Esse modelo recebe o nome de mochila 0/1 porque cada item possui somente duas possibilidades: 1, quando é selecionado, ou 0, quando não é selecionado. Um equipamento não pode ser fracionado nem escolhido mais de uma vez.

Uma seleção é válida quando a soma dos pesos não ultrapassa a capacidade. Entre todas as seleções válidas, uma solução ótima possui o maior valor total. A capacidade não precisa ser completamente preenchida.

Objetivo

Implemente uma solução para a mochila 0/1 por programação dinâmica com tabulação. O programa deve calcular o maior valor possível e reconstruir quais equipamentos formam uma solução ótima.

Para uma explicação mais detalhada do problema, da matriz e da reconstrução, consulte a aula de programação dinâmica.

Modelagem do problema

Considere n equipamentos apresentados na ordem da entrada e uma mochila com capacidade C. O equipamento de índice i possui peso p_i e valor v_i.

Use o estado dp[i][c] para representar o maior valor obtido com os primeiros i equipamentos e capacidade máxima c. A linha zero é o caso base, pois nenhum valor pode ser obtido sem equipamentos:

$$dp[0][c] = 0$$

Quando o equipamento i não cabe na capacidade c, copie a resposta da linha anterior. Quando ele cabe, compare deixá-lo de fora com selecioná-lo uma vez:

$$dp[i][c] = \begin{cases} dp[i-1][c], & \text{se } p_i > c \\ \max\left(dp[i-1][c],\ v_i + dp[i-1][c-p_i]\right), & \text{se } p_i \le c \end{cases}$$

As duas alternativas consultam a linha i - 1. Isso impede que o mesmo equipamento seja reutilizado e preserva a regra 0/1.

Depois do preenchimento, reconstrua a seleção a partir de dp[n][C]. Se dp[i][c] for diferente de dp[i-1][c], o equipamento i foi usado. Registre-o e reduza c por p_i. Caso contrário, avance para a linha anterior sem alterar a capacidade.

Em um empate entre usar e não usar o equipamento atual, mantenha a alternativa que não usa esse equipamento. Essa regra torna a saída reproduzível e favorece itens que apareceram antes na entrada.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: capacidade C e quantidade n de equipamentos;
2. próximas n linhas: identificador, peso e valor de cada equipamento.

Considere 0 <= C <= 10000, 1 <= n <= 100, 1 <= p_i <= 10000 e 1 <= v_i <= 1000000. Cada identificador deve possuir de 1 a 31 caracteres, sem espaços, e não pode se repetir.

8 4
A 2 3
B 3 4
C 4 5
D 5 8

Considere inválida uma entrada que viole os limites, repita um identificador, forneça menos ou mais equipamentos que o declarado ou contenha um valor não inteiro em um campo numérico. Informe o motivo e não apresente uma seleção parcial.

Regras essenciais

• Cada equipamento pode ser selecionado no máximo uma vez.
• Pesos e valores são independentes. Um equipamento mais pesado não precisa possuir maior valor.
• A soma dos pesos selecionados deve ser menor ou igual a C.
• O objetivo é maximizar o valor total, não o peso utilizado nem a quantidade de itens.
• A capacidade pode terminar com espaço livre quando essa for a seleção de maior valor.
• A solução deve preencher a matriz bidimensional dp por tabulação. Uma busca exaustiva, uma escolha gulosa ou apenas uma tabela unidimensional não substitui a técnica exigida neste projeto.
• A reconstrução deve usar as informações da matriz. Calcular somente o valor ótimo não atende ao projeto.
• Em empate, preserve a alternativa da linha anterior, sem o equipamento atual.
• Quando C = 0 ou nenhum equipamento couber, a seleção ótima é vazia e possui peso e valor iguais a zero.

Saída obrigatória

Liste os identificadores selecionados na ordem em que apareceram na entrada. Informe também o peso total, o valor total e a capacidade não utilizada.

Para a entrada de referência, a saída esperada é:

Itens selecionados: B D
Peso total: 8
Valor total: 12
Capacidade nao utilizada: 0

Exemplo visual da matriz e da reconstrução

A figura usa a entrada de referência. Cada linha libera um novo equipamento sem perder os anteriores. A célula final compara o valor 9 sem D com 8 + dp[3][3] = 12 usando D. A reconstrução identifica D, rejeita C e identifica B.

Casos para verificar

• Entrada de referência: use capacidade 8 e os quatro equipamentos apresentados. Confira a seleção B D, com peso 8 e valor 12.
• Capacidade zero: use pelo menos dois equipamentos válidos e C = 0. Confira seleção vazia e totais iguais a zero.
• Nenhum equipamento cabe: use equipamentos cujos pesos sejam todos maiores que a capacidade. Confira seleção vazia, mesmo que os valores sejam altos.
• Empate reproduzível: use capacidade 4 e os itens A 4 6, B 2 3 e C 2 3, nessa ordem. As seleções A e B C possuem peso 4 e valor 6; confira que a regra de empate preserva A.
• Capacidade não preenchida: use capacidade 6 e os itens A 4 10, B 5 12 e C 6 11. Confira que B é escolhido sozinho, com uma unidade de capacidade livre, pois possui o maior valor.

Para cada caso, registre a entrada, a saída obtida e uma verificação manual curta. Confirme que cada item aparece no máximo uma vez, que o peso respeita a capacidade e que nenhuma seleção alternativa possui valor maior.

Limite do projeto

O núcleo do projeto inclui validar a entrada, preencher a matriz dp, reconstruir uma seleção ótima e executar os casos de verificação. Trabalhe somente com pesos, valores e capacidade inteiros.

Não são exigidos itens fracionários, múltiplas unidades do mesmo item, pesos decimais, várias mochilas, escolha gulosa, força bruta, memoização, otimização da matriz para uma única linha ou comparação de desempenho entre implementações.