Exercícios resolvidos: programação dinâmica no troco mínimo

Explicação

A regra pega 5 primeiro e só consegue completar o restante 3 com fichas de 1. Uma alternativa com duas fichas de 4 reduz a quantidade. Não há ficha de valor 8, então uma solução com apenas uma ficha não existe.

Objetivo de aprendizagem: encontrar um contraexemplo para decidir quando a escolha local não serve como método de solução.

Resposta esperada

A regra gulosa entrega 5 + 1 + 1 + 1, com quatro fichas. A entrega 4 + 4 usa duas fichas e forma exatamente 8. Como não existe ficha de valor 8, duas é a quantidade mínima.

Explicação

As três sequências retiram 4 unidades do pedido. Como o estoque é ilimitado, os caminhos deixam exatamente os mesmos tipos de ficha disponíveis. A quantidade de fichas já usadas difere, mas a melhor resposta para o restante é a mesma.

Objetivo de aprendizagem: identificar subproblemas sobrepostos pela pergunta que permanece para evitar recalcular a mesma resposta.

Resposta esperada

Todos os caminhos deixam 3 unidades para formar: 7 - 1 - 3 = 3, 7 - 3 - 1 = 3 e 7 - 4 = 3. A menor quantidade de fichas para esse restante pode ser calculada uma vez e reutilizada. Os totais dos caminhos completos ainda somam as fichas já usadas em cada um.

Explicação

As duas formas produzem o mesmo restante de 10. Substituir quatro fichas por duas mantém a soma e reduz a quantidade da entrega completa. Logo, uma entrega ótima não pode conservar um restante que admite uma solução melhor.

Objetivo de aprendizagem: justificar por substituição por que a solução ótima pode usar a melhor resposta para um valor restante.

Resposta esperada

O plano original é 5 + 3 + 1 + 1 + 1, com cinco fichas. Substituir o restante por 5 + 5 produz 5 + 5 + 1, com três fichas. Portanto, se uma entrega ótima termina com 1, as outras fichas precisam formar as 10 unidades restantes com a menor quantidade possível.

Explicação

O estado responde uma quantidade mínima, não uma lista de fichas. Para formar zero, a entrega vazia é válida e custa zero. Já 1 e 2 não podem ser formados com fichas de 3 e 4. Um marcador como ∞ separa impossibilidade do custo válido zero.

Objetivo de aprendizagem: definir o estado e distinguir caso base de impossibilidade para que a tabela represente respostas corretas.

Resposta esperada

F(value) é a menor quantidade de fichas que forma exatamente value. Temos F(0) = 0, F(1) = ∞ e F(2) = ∞. O zero significa uma entrega válida sem fichas; ∞ significa que nenhuma entrega forma o valor.

Explicação

A última ficha acrescenta uma unidade à quantidade de fichas necessária para o restante. As duas escolhas produzem o mesmo custo. Como o empate não substitui a decisão anterior, fica registrado o índice da ficha testada primeiro.

Objetivo de aprendizagem: aplicar a transição do troco mínimo e registrar uma decisão que permita reconstruir a entrega.

Resposta esperada

Assim, F(7) = 2 e last_coin[7] = 0. O índice 0 identifica a ficha de valor 3.

Explicação

Cada linha usa somente restos menores já resolvidos. Um resto impossível não produz candidata. Em 7, as duas últimas fichas possíveis geram a mesma quantidade, então o índice 0 permanece.

Objetivo de aprendizagem: avançar na tabulação sem consultar respostas futuras e registrar empates de modo reproduzível.

Resposta esperada

Explicação

O índice localiza uma posição em coins. O valor nominal dessa posição é subtraído do restante. Cada ficha positiva diminui o restante, e a sequência termina quando ele chega a zero.

Objetivo de aprendizagem: reconstruir uma entrega a partir das decisões guardadas sem confundir índice com valor nominal.

Resposta esperada

A entrega é 3 + 3 + 5 = 11, com três fichas.

Explicação

Formar 3 com uma ficha produz a candidata 1. Como 1 não é menor que o zero indevidamente armazenado em F(3), a atualização não acontece. Zero deve ficar reservado ao caso base; as demais posições começam com um marcador que não se confunde com custo válido.

Objetivo de aprendizagem: detectar como uma representação incorreta impede atualizações válidas e separar custo zero de impossibilidade.

Resposta esperada

A candidata para F(3) é 1, mas a comparação 1 < 0 é falsa. O programa mantém incorretamente F(3) = 0. A correção é reservar zero ao caso base e iniciar as demais posições com um marcador de impossibilidade, como ∞. Antes de somar 1 a um resto, é preciso verificar se ele não está marcado como impossível.

Explicação

As fichas 3 e 4 deixam restos 4 e 3. Nenhum deles foi calculado no plano proposto. Como cada ficha é positiva, toda dependência tem valor menor que o estado atual. Avançar a partir do caso base respeita essa direção.

Objetivo de aprendizagem: escolher uma ordem de tabulação que respeite as dependências e evite consultar respostas futuras.

Resposta esperada

F(7) precisaria de F(4) e F(3), ainda ausentes. O plano deve preencher os valores em ordem crescente, começando em F(1) após o caso base e seguindo até F(7). Estados impossíveis também recebem uma resposta definitiva antes de serem consultados.

Explicação

As primeiras chamadas descem por 7 → 5 → 3 → 1. O estado 1 é impossível e recebe essa resposta no cache. A função só guarda F(3) após conferir as duas fichas. Mais tarde, o cálculo de F(4) encontra F(2) já pronto.

Objetivo de aprendizagem: distinguir chamada, conclusão e reutilização de estados para rastrear corretamente o cache recursivo.

Resposta esperada

Os estados não base entram no cache nesta ordem: F(1), F(3), F(2), F(5), F(4), F(7). F(1) é armazenado como impossível. O primeiro acerto de cache não base é F(2), consultado durante o cálculo de F(4).

Explicação

As duas técnicas reutilizam respostas. A tabulação começa no caso base e preenche a faixa planejada. A memoização começa no pedido e só resolve estados alcançados, embora o vetor de cache ainda reserve posições para todo o intervalo.

Objetivo de aprendizagem: escolher entre memoização e tabulação pelo padrão de consultas, considerando cálculo e memória reservada.

Resposta esperada

1. Tabulação: calcula todos os valores de 0 a 100 em ordem crescente, exatamente o que o painel precisa, sem pilha recursiva.
2. Memoização: a partir de 120, só precisa resolver os valores 120, 80, 60, 40, 20 e 0. O vetor de cache ainda reserva posições de 0 a 120 e a recursão usa pilha.

Explicação

Há uma posição para cada valor de zero ao pedido. Os testes ocorrem nos estados não base. As duas tabelas têm o mesmo comprimento. A comparação com o orçamento considera bytes, sem arredondar para megabytes.

Objetivo de aprendizagem: estimar trabalho e memória da tabulação para decidir se ela cabe nos recursos disponíveis.

Resposta esperada

São 500.001 estados, 3.000.000 testes de ficha e 8.000.016 bytes nas duas tabelas: 2 × 500.001 × 8. Elas não cabem nos 7.500.000 bytes reservados. Faltam 500.016 bytes. O tempo é O(amount × coin_count) e o espaço das tabelas é O(amount).

Explicação

O algoritmo percorre valores numéricos até um milhão, apesar de esse número caber em aproximadamente 20 bits. Em geral, b bits podem representar valores próximos de 2^b; a tabela pode crescer exponencialmente em relação a b.

Objetivo de aprendizagem: distinguir custo no valor numérico e no tamanho da entrada para reconhecer o limite pseudopolinomial.

Resposta esperada

O tempo é polinomial em amount, mas pode ser exponencial na quantidade de bits que representa esse número. Para um valor com b bits, amount pode ser da ordem de 2^b. Por isso, O(amount × coin_count) é chamado de pseudopolinomial.

Explicação

O marcador de impossibilidade não pode participar da soma. Uma candidata válida acrescenta uma moeda ao custo do restante. A comparação estrita preserva a primeira escolha quando há empate e mantém custo e índice coerentes.

Objetivo de aprendizagem: atualizar custo e escolha em C sem somar ao marcador de impossibilidade nem registrar um empate como melhora.

Resposta esperada

// Apenas um restante possível produz uma candidata.
if (previous != SIZE_MAX) {
    size_t candidate = previous + 1U;

    // Atualize custo e índice somente quando a candidata melhorar.
    if (candidate < best) {
        best = candidate;
        chosen_index = coin_index;
    }
}

Explicação

Ambos os caminhos já usam 6 unidades e deixam 4. No caminho A, a ficha de 4 continua disponível. No caminho B, ela e a ficha de 2 foram consumidas, restando somente fichas de 3. O mesmo valor restante pode ter respostas diferentes.

Objetivo de aprendizagem: ampliar o estado quando o estoque altera a resposta para o mesmo valor restante e evitar reutilização incorreta.

Resposta esperada

Os caminhos não representam o mesmo subproblema. Ambos deixam 4 unidades, mas A ainda dispõe da ficha de 4 e pode concluir a entrega; B dispõe apenas de duas fichas de 3 e não consegue formar 4. O estado precisa registrar o valor restante e o estoque remanescente de cada tipo de ficha. Guardar a resposta apenas por valor restante misturaria situações diferentes.