LogRitmo navegador / ativofase / 03LR / fase 03 · ativaTrocar trabalho repetido por estados explícitos e transições verificáveis.
Antes de considerar itens, a capacidade vazia tem valor zero. Esse caso base ancora as próximas transições.
princípio /
Subestrutura ótima e subproblemas sobrepostos permitem guardar respostas parciais e reutilizá-las.
limite que não pode ser omitido
Dynamic Programming não é apenas usar uma tabela. É necessário definir um estado que represente o problema e uma transição que preserve a resposta correta.
Aqui, n é o número de itens e C representa a capacidade discreta da mochila visualizada.
Há dois eixos: n é o número de itens e C é a capacidade ou quantidade de estados possíveis. O algoritmo avalia combinações desses dois limites.
Aumentar apenas n ou apenas C aumenta o trabalho; aumentar os dois multiplica a quantidade de estados examinados.Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Use este par para contrastar uma escolha local eficiente com o custo de preencher e reutilizar estados em problemas de capacidade. Greedy Algorithm e Dynamic Programming usam parâmetros diferentes: O(n·C) depende da capacidade C, e O(bᵈ) depende da ramificação b e da profundidade d. A régua contrasta modelos de crescimento; só compare a inclinação sob hipóteses explícitas sobre como esses parâmetros aumentam.
O destaque acompanha a decisão atual. Leia o pseudocódigo antes de trocar de linguagem; a implementação é uma tradução, não um novo algoritmo.
01const table = Array(capacity + 1).fill(0); // Initialize one state for each capacity02for (const item of items) {03 for (let limit = capacity; limit >= item.weight; limit--) {04 table[limit] = Math.max(table[limit],05 table[limit - item.weight] + item.value06 );07 }08}09return table[capacity];Dynamic Programming formula uma família de subproblemas, registra o valor de cada estado e reutiliza esse resultado quando a mesma situação reaparece. A tabela não é a estratégia; ela é apenas uma forma de materializar uma recorrência que já precisa estar bem definida.
Um estado deve reter apenas a informação necessária para decidir o restante. Em Knapsack 0/1, item considerado e capacidade residual importam; em LCS, os dois prefixos importam. Omissões tornam a transição incorreta.
A recorrência transforma respostas menores em uma resposta atual. Ela precisa cobrir todas as alternativas permitidas — por exemplo, incluir ou excluir um item — e combinar seus valores de acordo com o objetivo de minimizar, maximizar ou contar.
Casos-base corretos e uma ordem de avaliação válida sustentam a prova por indução. Em uma tabela, cada consulta deve apontar para um estado já calculado; em memoização, a chamada recursiva preenche a dependência sob demanda.
A faixa colorida representa valores armazenados para estados menores. Ela mostra reuso, não uma prova automática de optimalidade: a garantia depende de o estado distinguir todos os futuros relevantes e de a transição preservar o valor correto para cada célula.
Antes de escrever loops, declare a unidade de progresso, o valor procurado, as decisões que levam a ele e a informação que modifica essas decisões. Essa disciplina separa Dynamic Programming de uma matriz preenchida por tentativa e erro.
Memoização e tabulação devem devolver o mesmo valor quando partem da mesma recorrência correta. A escolha entre elas altera quais estados são visitados, o uso da pilha, a facilidade de depuração e a forma de reconstruir decisões — não o problema matemático resolvido.
Uma estimativa útil é número de estados alcançados × custo por transição. Na mochila com capacidade C, o custo O(n·C) depende do valor numérico de C; portanto, é pseudo-polinomial quando C chega codificado em binário. O espaço inclui a tabela, o cache e, se necessário, predecessores para reconstrução.
Use Dynamic Programming quando subproblemas se sobrepõem e a recorrência possui subestrutura ótima. Prefira Divide and Conquer quando as chamadas são independentes; prefira Greedy apenas quando houver uma escolha local segura provada. Documente a dimensão do estado, a ordem de preenchimento, o custo de memória e se a compressão de espaço ainda permite reconstruir a solução desejada.