Exercícios resolvidos: força bruta e estratégia gulosa

Explicação

Um subconjunto é viável quando nenhum par se sobrepõe. Os limites são semiabertos, então A e B são compatíveis porque A termina no instante em que B começa.

Resposta esperada

1. {A, B, D} é viável e contém três atividades.
2. {A, C, D} é inviável porque A e C se sobrepõem. O subconjunto contém três atividades, mas não constitui uma solução válida.
3. {B, C, D} é inviável porque B e C se sobrepõem. O subconjunto contém três atividades, mas não constitui uma solução válida.

Explicação

A garantia da força bruta vem da busca completa. Uma estratégia gulosa examina menos candidatos, por isso precisa de uma justificativa específica. Para a seleção de atividades, o argumento de troca sustenta a regra do menor término.

Resposta esperada

1. Correta. A solução ótima está entre os subconjuntos examinados e será comparada com as demais soluções viáveis.
2. Incorreta. Uma regra local pode ser rápida e ainda bloquear uma solução global melhor.
3. Correta. Trocar a primeira atividade de uma solução ótima pela atividade que termina mais cedo não bloqueia as atividades seguintes.

Explicação

Cada bit igual a 1 inclui sua atividade. A leitura precisa respeitar a correspondência D C B A da esquerda para a direita.

Resposta esperada

1. 0000 corresponde a {}.
2. 0101 corresponde a {A, C}.
3. 1010 corresponde a {B, D}.
4. 1101 corresponde a {A, C, D}.

Explicação

Cada atividade possui duas decisões independentes: entrar ou não entrar. Para dez atividades, isso produz $2^{10}$ subconjuntos. A verificação completa de um subconjunto considera todos os pares possíveis.

Resposta esperada

1. $2^{10} = 1.024$ subconjuntos.
2. $10(10 - 1) / 2 = 45$ pares por subconjunto.
3. No máximo $1.024 \times 45 = 46.080$ comparações de pares nessa contagem. Para n atividades, a ordem é $O(n^2 2^n)$.

Explicação

Duas atividades são compatíveis quando a primeira termina antes do início da segunda ou quando a segunda termina antes do início da primeira. A igualdade precisa ser aceita por causa dos intervalos semiabertos.

Resposta esperada

static bool are_compatible(const activity *first, const activity *second) {
    return first->finish <= second->start || second->finish <= first->start;
}

Explicação

Existem $2^4 = 16$ subconjuntos candidatos. Um conflito em qualquer par torna todo o subconjunto inviável. Entre os pares, A é compatível com C porque A termina em 2 e C começa em 2.

Resposta esperada

Os subconjuntos viáveis são:

{}
{A}
{B}
{C}
{D}
{A, C}
{A, D}
{B, D}
{C, D}
{A, C, D}

A solução ótima é {A, C, D}, com três atividades. Nenhum outro subconjunto viável possui três ou quatro atividades.

Explicação

A ordem é L, M, N, O, K, P. A primeira atividade é aceita. Depois disso, uma atividade somente é aceita quando start >= last_finish. Uma rejeição não altera last_finish.

Resposta esperada

L = [1, 3): aceitar, last_finish = 3
M = [3, 5): aceitar, last_finish = 5
N = [0, 7): rejeitar, last_finish = 5
O = [5, 7): aceitar, last_finish = 7
K = [5, 9): rejeitar, last_finish = 7
P = [8, 10): aceitar, last_finish = 10

O resultado é {L, M, O, P}, com quatro atividades.

Explicação

Sem ordenação, K = [5, 9) é aceita primeiro. Todas as demais atividades começam antes de 9, inclusive P, que começa em 8. O resultado continua viável, mas perde a garantia de quantidade máxima.

Resposta esperada

K = [5, 9): aceitar, last_finish = 9
L = [1, 3): rejeitar, last_finish = 9
M = [3, 5): rejeitar, last_finish = 9
N = [0, 7): rejeitar, last_finish = 9
O = [5, 7): rejeitar, last_finish = 9
P = [8, 10): rejeitar, last_finish = 9

O resultado sem ordenação é {K}, com uma atividade. A condição violada foi a ordenação prévia por término crescente. Como essa etapa foi ignorada, as atividades foram processadas na ordem de entrada, e não da que termina mais cedo para a que termina mais tarde. Com a ordenação, o exercício 7 seleciona quatro atividades.

Explicação

G termina em 3, antes de X, que termina em 4. As atividades posteriores começam em 4 ou depois. Portanto, tudo que cabia após X também cabe após G.

Resposta esperada

A troca produz {G, Y, Z}. O novo conjunto continua viável e mantém três atividades. Como finish(G) <= finish(X), a troca não bloqueia Y nem Z. Isso demonstra que existe uma solução ótima iniciada pela escolha gulosa G.

Explicação

A regra escolhe A porque ela começa em 0. Essa atividade ocupa todo o período usado pelas outras atividades. Para refutar a garantia, basta apresentar uma solução viável com valor do objetivo maior.

Resposta esperada

A regra do menor início produz {A}, com uma atividade. O conjunto {B, C, D, E} é viável e contém quatro atividades. Portanto, essa entrada é um contraexemplo e a regra do menor início não garante uma solução ótima.

Explicação

O deslocamento posiciona um único bit para representar uma atividade. A operação mask & bit preserva esse bit somente quando ele também vale 1 na máscara. Resultado zero significa ausência; resultado diferente de zero significa presença.

Resposta esperada

Portanto, a máscara 0101 representa o subconjunto {A, C}.

Explicação

Cada repetição processa exatamente uma posição. O bit lido vale 0 ou 1 e pode ser somado diretamente a count. O deslocamento prepara a posição seguinte para a próxima repetição.

Resposta esperada

A máscara contém três bits ativos, portanto representa um subconjunto com três atividades.

Explicação

Os exercícios anteriores já estabeleceram a representação dos subconjuntos, a verificação de compatibilidade, a busca completa e a escolha gulosa. A implementação integra essas operações em funções separadas e usa a mesma entrada para tornar os resultados comparáveis.

A solução de referência usa qsort, mas esse mecanismo específico não é obrigatório. Qualquer ordenação correta por término crescente preserva o método guloso estudado.

Resposta esperada

Para as atividades do exercício 7, as duas estratégias devem selecionar quatro atividades compatíveis:

Força bruta (4 atividades):
  L: [1, 3)
  M: [3, 5)
  O: [5, 7)
  P: [8, 10)

Guloso (4 atividades):
  L: [1, 3)
  M: [3, 5)
  O: [5, 7)
  P: [8, 10)

Compare a implementação com a solução completa em C.