Programação dinâmica

Definir estado antes de preencher

Escreve significado da célula, bases, alternativas e ordem com dependências prontas. Memoização evita inalcançáveis; tabulação explicita ordem. Custo é estados vezes trabalho por estado.

Tabelas essenciais

$F$ é valor da mochila, $C$ é número de moedas, $B$ é existência booleana e $E$ é melhor soma terminada em $i$. O objeto $i$ tem peso $p_i$ e valor $v_i$; a moeda $i$ tem valor facial $c_i$ e stock $s_i$. $W$ é a capacidade da mochila, $T$ é o alvo de soma ou trocos, $S=\max s_i$ é o maior stock e $q$ é a quantidade usada da denominação atual.

Problema	Estado e transição	Custo
Mochila 0-1	$F[i,w]=\max(F[i-1,w],v_i+F[i-1,w-p_i])$ se $p_i\le w$; senão $F[i-1,w]$	$O(nW)$
Trocos ilimitados	$C[i,t]=\min(C[i-1,t],1+C[i,t-c_i])$; ignora a segunda se $t<c_i$	$O(nT)$
Trocos com stock	$\min_q(q+C[i-1,t-qc_i])$ com $0\le q\le\min(s_i,\lfloor t/c_i\rfloor)$	$O(nT(S+1))$ direto
Soma de subconjuntos	$B[i,t]=B[i-1,t]\lor(t\ge a_i\land B[i-1,t-a_i])$	$O(nT)$
Subvetor não vazio	$E[i]=\max(A[i],E[i-1]+A[i])$ com $E[0]=A[0]$; resposta é o máximo global	$O(n)$

Bases: mochila zero; trocos com alvo zero custa zero e alvo positivo sem moedas custa infinito; soma com $B[0,0]$ verdadeiro. Reconstruir exige pais ou decisões; vetor único economiza espaço mas apaga histórico.

Regras que evitam erros

• Linha anterior impede repetir objeto na 0-1. Percorre $w$ por ordem decrescente no vetor único; crescente resolveria a ilimitada.
• Com 1 objeto de peso 2 e valor 3, com $W=4$, percorrer $w$ por ordem crescente dá 6 por reutilizar o objeto duas vezes; por ordem decrescente dá 3, o valor correto da mochila 0-1.
• $O(nW)$ e $O(nT)$ são pseudopolinomiais com $W,T$ em binário.
• DAG com destino $t$: $D[t]=0$, $D[u]=\min_{u\to v}(w+D[v])$ em ordem inversa; sem caminho mantém infinito.
• Combinações: $\binom nk=\binom{n-1}{k-1}+\binom{n-1}k$; reduz memória com $k$ decrescente.

Recorrências e reconstrução.