Programação dinâmica

Na mochila de capacidade 7 com objetos $A=(2,3)$, $B=(3,4)$, $C=(4,5)$ e $D=(5,8)$, a decisão sobre $D$ separa dois subproblemas: incluir $D$ deixa capacidade 2 para os outros objetos, excluí-lo deixa capacidade 7. Cada par indica peso e valor. A programação dinâmica guarda a resposta a cada subproblema de objetos e capacidade, para não recalcular a mesma escolha muitas vezes.

O estado precisa de informação suficiente para determinar as continuações permitidas. Uma solução ótima contém soluções ótimas desses subproblemas: substituir uma parte por outra melhor tem de conservar as restrições da solução completa. É essa propriedade de substituição que justifica cada recorrência desta lição.

Definir antes de preencher

Para derivar uma tabela, escreve o significado exato de uma célula, os casos base e as alternativas que levam até ela. Decide a ordem em que as dependências ficam disponíveis. Por fim, guarda informação para reconstruir uma solução, quando o enunciado pede mais do que o valor.

Memoização calcula estados por chamadas e guarda-os na primeira visita. Tabulação calcula-os por uma ordem pré-definida, normalmente crescente num índice. A primeira pode evitar estados inalcançáveis; a segunda evita parte do custo das chamadas e torna a ordem explícita. Nenhuma é sempre mais rápida.

A complexidade resulta do número de estados multiplicado pelo trabalho por estado, mais inicialização e reconstrução.

Vídeo complementar em inglês: Programação dinâmica, Fibonacci e caminhos mínimos, aula 19 de 6.006, 2011 (MIT OpenCourseWare). Para passar de recursão repetida a estados guardados, identifica o significado de cada subproblema e conta os estados distintos, em vez das chamadas repetidas.

Mochila 0-1

Define $F[i,w]$ como o valor máximo usando os primeiros $i$ objetos, com capacidade disponível $w$. Não exige preencher a mochila. Assumimos pesos inteiros positivos e valores não negativos.

Se o objeto $i$ tem peso $p_i$ e valor $v_i$, ou o excluímos, ou o incluímos uma vez:

Os casos base são $F[0,w]=0$ e $F[i,0]=0$. A linha anterior impede usar o mesmo objeto outra vez. As duas alternativas cobrem todas as soluções; dentro de cada alternativa, substituir o subconjunto restante por um melhor conserva a capacidade. Isto prova a recorrência.

Usamos os objetos $A=(2,3)$, $B=(3,4)$, $C=(4,5)$, $D=(5,8)$ e $W=7$:

Na última célula, excluir $D$ dá $F[3,7]=9$; incluí-lo dá $8+F[3,2]=8+3=11$. O valor máximo é 11.

Reconstruir objetos

Começa em $(i,w)=(4,7)$. Como $F[4,7]\ne F[3,7]$, escolhemos $D$ e passamos para $(3,2)$. As linhas de $C$ e $B$ não melhoraram a capacidade 2, por isso excluímos esses objetos. A linha de $A$ melhora de zero para 3, portanto escolhemos $A$. A solução tem peso 7 e valor 11.

Se as duas alternativas empatam, excluir o objeto é uma regra válida para devolver um ótimo. Minimizar também o peso ou a quantidade de objetos exige guardar e comparar esse segundo critério.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    int n, W;
    if (!(std::cin >> n >> W) || n < 0 || n > 100 || W < 0 || W > 2000) {
        std::cout << "entrada invalida\n";
        return 0;
    }
    std::vector<int> peso(n + 1);
    std::vector<long long> valor(n + 1);
    for (int i = 1; i <= n; ++i) {
        if (!(std::cin >> peso[i] >> valor[i]) || peso[i] < 1 || peso[i] > 2000 ||
            valor[i] < 0 || valor[i] > 1000000) {
            std::cout << "entrada invalida\n";
            return 0;
        }
    }
    std::vector<std::vector<long long>> f(n + 1, std::vector<long long>(W + 1));
    for (int i = 1; i <= n; ++i)
        for (int w = 0; w <= W; ++w) {
            f[i][w] = f[i - 1][w];
            if (peso[i] <= w)
                f[i][w] = std::max(f[i][w], valor[i] + f[i - 1][w - peso[i]]);
        }
    std::vector<int> escolhidos;
    for (int i = n, w = W; i > 0; --i) {
        if (f[i][w] == f[i - 1][w]) continue;
        escolhidos.push_back(i);
        w -= peso[i];
    }
    std::reverse(escolhidos.begin(), escolhidos.end());
    std::cout << "valor " << f[n][W] << "\nobjetos";
    for (int i : escolhidos) std::cout << ' ' << i;
    std::cout << '\n';
}

O programa lê n W, seguido de peso valor, e devolve valor 11 e objetos 1 4. Os objetos são numerados a partir de 1. Aceita até 100 objetos, capacidade até 2000, pesos positivos até 2000 e valores de 0 a um milhão.

Há $(n+1)(W+1)$ estados, com trabalho constante: $\Theta(nW)$ tempo e $\Theta(nW)$ espaço. A reconstrução custa $O(n)$. Se só precisamos do valor, podemos conservar um vetor e percorrer capacidades por ordem decrescente. Assim F[w-p_i] ainda pertence à iteração anterior. Percorrer por ordem crescente permitiria repetir o objeto e resolveria a mochila ilimitada.

O que significa pseudopolinomial

$O(nW)$ é polinomial em $n$ e no valor de $W$, mas a entrada representa $W$ com $O(\log(W+1))$ bits. Se $W=2^k$, a tabela tem $2^k$ colunas para uma capacidade representada com cerca de $k$ bits. Chamamos a este custo pseudopolinomial.

Não há contradição com a dificuldade NP-completa da versão de decisão da mochila: para capacidades pequenas, a tabela pode ser prática; para valores enormes, força bruta em poucos objetos ou outro método pode usar menos trabalho.

Trocos ilimitados e com stock

Para denominações inteiras positivas $c_1,\ldots,c_n$ e quantidade ilimitada, define $C[i,t]$ como o mínimo de moedas para pagar exatamente $t$ usando as primeiras $i$ denominações. Temos $C[i,0]=0$ e $C[0,t]=+\infty$ para $t>0$.

ignorando a segunda alternativa se $t<c_i$. A mesma linha $i$ permite reutilizar a denominação. Uma célula infinita significa impossível, não zero moedas. O tempo é $O(nT)$ e o espaço é $O(nT)$, ou $O(T)$ para o valor.

Com moedas 1, 3 e 4, os valores mínimos para alvos de 0 a 6 são $0,1,2,1,1,2,2$. Para 6, a recorrência prefere $3+3$ ao guloso $4+1+1$.

Se o stock de $c_i$ é $s_i$, o estado deve respeitá-lo:

Aqui a linha anterior é necessária: escolhemos toda a quantidade $q$ dessa denominação uma vez.

Conservamos as moedas $1,3,4$, stocks $2,2,1$ e alvo 6 usados na força bruta. Com apenas duas moedas de 1, $C[1,6]=+\infty$. Na linha da moeda 3, as alternativas para o alvo 6 são:

Na linha da moeda 4, não a usar conserva 2. Usar uma deixa alvo 2, com custo $1+C[2,2]=3$. Vence a primeira alternativa. Para reconstruir, guardamos $q=0$ na linha de 4, $q=2$ na linha de 3 e $q=0$ na linha de 1. Obtemos $3+3$, as mesmas duas moedas encontradas por enumeração.

A formulação direta testa até $S+1$ quantidades por célula, para stock máximo $S$, e custa $O(nT(S+1))$ tempo e $O(nT)$ espaço. Otimizações da mochila limitada podem reduzir o trabalho, preservando o significado do estado.

Soma de subconjuntos

Com inteiros não negativos $a_i$, define $B[i,t]$ como “há um subconjunto dos primeiros $i$ elementos com soma $t$”. Inicializa $B[0,0]$ a verdadeiro e os outros a falso:

É a mesma decisão incluir/excluir, agora com existência em vez de máximo. O custo é $O(nT)$. Para reconstruir, se a célula da linha anterior já é verdadeira, podemos excluir; caso contrário incluímos $a_i$ e reduzimos $t$. Elementos zero exigem uma regra de desempate, mas não tornam a existência incorreta.

O subvetor máximo em tempo linear

Define $E[i]$ como a maior soma de um intervalo não vazio que termina em $i$. Esse intervalo ou começa em $i$, ou prolonga o melhor terminado em $i-1$:

O resultado global é $\max_i E[i]$. Esta é a forma dinâmica do algoritmo de Kadane. Guarda o início do intervalo atual: reinicia em $i$ quando escolher $A[i]$ sozinho; atualiza os extremos globais quando melhora o máximo.

Para [-4,3,-1,5,-6,2], compara o melhor intervalo terminado em cada posição com o melhor já encontrado:

No índice 4, o melhor intervalo terminado ali vale 1, mas o máximo já encontrado continua a ser 7. Só um intervalo terminado no índice anterior pode ser prolongado sem saltar elementos. O máximo é 7 e termina no índice 3, com início 1. Se todos os valores forem negativos, conserva o maior deles. A recorrência tem $n$ estados e trabalho constante, portanto $O(n)$ tempo e $O(1)$ memória auxiliar para valor e extremos.

Caminhos por etapas e combinações

Num DAG com destino $t$, define $D[t]=0$ e

Para $u\ne t$, processa em ordem topológica inversa; um vértice sem caminho até $t$ mantém infinito. Não atualizes $D[t]$ pelas suas saídas: o caminho procurado já terminou em $t$. Os subcaminhos repetidos ficam guardados e o custo é $O(n+m)$. Um estado que omitisse o vértice atual não distinguiria continuações diferentes.

Para combinações com $0\le k\le n$, $\binom nk=\binom{n-1}{k-1}+\binom{n-1}k$, com $\binom n0=\binom nn=1$ e $\binom ij=0$ para $j>i$. As parcelas representam incluir ou excluir um elemento fixo. Uma tabela até $(n,k)$ usa $O(nk)$ operações; os valores podem exigir inteiros grandes. Ao reduzir a memória a uma linha, percorre $k$ por ordem decrescente para não misturar linhas.