estratégia / memória de estados
próxima lente Programação dinâmica (Dynamic Programming).
Trocar trabalho repetido por estados explícitos e transições verificáveis.
visualização passo a passo
stage / DPO que já calculamos pode responder a uma decisão nova?
001
002
003
004
005
006
foco atual / inicializar o estadoa faixa mostra o estado, não uma medição de tempo real
ação / progresso comparação / estado conflito / limite
telemetria / estratégia
passo01inicializar o estado
estadobaseestado observado
códigolinha 1JavaScript
estadopausadocontrole manual
/ o que está acontecendoinicializar o estado
inicializar o estado
reutilize a evidência.
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
Programação dinâmica não é apenas usar uma tabela. É necessário definir um estado que represente o problema e uma transição que preserve a resposta correta.
complexidade / mapa rápido
melhorO(n·C)
médioO(n·C)
piorO(n·C)
Aqui, n é o número de itens e C representa a capacidade discreta da mochila visualizada.
/ por baixo do palco
Uma memória, um estado.
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.
01tabela[0][capacidade] ← 0
02para cada item:
03 para capacidade decrescente:
04 sem_item ← tabela anterior
05 com_item ← valor + estado restante
06 tabela ← máximo dos dois
implementação / JavaScript
01const table = Array(capacity + 1).fill(0);02for (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}