Mochila 0/1 e otimização de espaço

O problema da mochila 0/1: dados n itens, cada um com um peso w[i] e um valor v[i], e uma mochila com capacidade W, escolha itens para maximizar o valor total sem exceder a capacidade. Cada item é escolhido exatamente uma vez (0 = não escolher, 1 = escolher). Este é o modelo clássico de uma grande família de problemas de DP em entrevistas, incluindo soma de subconjunto com partições iguais e soma-alvo.

Defina dp[i][c] como o valor máximo obtido usando os primeiros i itens com capacidade c. Há duas opções para o item i: não escolhê-lo (dp[i-1][c]) ou escolhê-lo se w[i] <= c (dp[i-1][c-w[i]] + v[i]). A recorrência é: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) quando w[i] <= c; caso contrário, dp[i][c] = dp[i-1][c]. Caso base: dp[0][c] = 0 para todo c.

A tabela 2D tem (n+1) x (W+1) entradas e é preenchida linha por linha para cada item. Depois que todas as linhas forem preenchidas, dp[n][W] conterá o valor máximo. Isso leva O(n × W) de tempo e usa O(n × W) de espaço — uma complexidade pseudo-polinomial eficiente quando W é pequeno.

A observação fundamental é que a linha i depende apenas da linha i-1. Portanto, podemos usar um único vetor 1D e atualizá-lo no próprio lugar. No entanto, se percorrermos a capacidade c da esquerda para a direita (do menor para o maior valor), o item i poderá ser contado duas vezes — poderíamos usar o valor atualizado de c-w[i], que já inclui o item i. Percorrer da direita para a esquerda (do maior para o menor valor) garante que cada item seja usado no máximo uma vez em cada atualização de linha.

Mantendo apenas um vetor e percorrendo a capacidade de W até w[i] em ordem decrescente, obtemos o mesmo resultado da tabela 2D usando O(W) de espaço. A complexidade de tempo continua sendo O(n × W). Essa otimização de espaço é essencial para memorizar — entrevistadores pedem com frequência que você reduza a mochila 2D para 1D.

Para descobrir quais itens foram selected, é necessário ter a tabela 2D completa. Depois de preenchê-la, comece em dp[n][W] e percorra-a de trás para frente: se dp[i][c] != dp[i-1][c], o item i foi incluído — subtraia seu peso de c e passe para a linha i-1. Continue até i = 0. A otimização 1D elimina essa capacidade de reconstrução.

Considere os itens: weights=[2,3,4,5], values=[3,4,5,6], W=8. A solução ideal é escolher os itens com peso 3 (valor 4) e peso 5 (valor 6) — peso total 8 e valor 10. Outra opção seria escolher os pesos 2 e 5 — valor total 9. Ou os pesos 2 e 3 — valor 7. A DP encontra corretamente o valor máximo, 10. Observe que a abordagem gulosa (escolher a maior proporção entre valor e peso) escolheria primeiro o item com proporção 1,5 (peso 2, valor 3) — o que nem sempre é ideal.

Na mochila fracionária, é possível escolher frações dos itens. Esse problema pode ser resolvido de forma gulosa, ordenando os itens pela proporção entre valor e peso. Na mochila 0/1, os itens são indivisíveis — a abordagem gulosa falha, e é necessário usar DP. Entrevistadores usam essa distinção para verificar se você sabe quando a abordagem gulosa é aplicável. Se perguntarem sobre a variante fracionária, mencione imediatamente a abordagem gulosa com ordenação; se for 0/1, recorra à DP.

A mochila 0/1 é NP-completa, mas ainda assim conseguimos resolvê-la em tempo O(nW). A contradição se explica porque O(nW) é pseudo-polinomial: W é um valor, não o tamanho da entrada. A representação binária de W ocupa O(log W) bits, portanto a complexidade verdadeira é O(n × 2^(log W)), que é exponencial em relação ao tamanho da entrada. Quando W é pequeno (por exemplo, 10⁴), a DP é prática; quando W pode ser 10⁹, precisamos de abordagens diferentes.

Se o entrevistador impuser que W seja muito grande (por exemplo, 10⁹), mas n seja pequeno, a DP padrão deixará de ser viável. As alternativas incluem: (1) divisão ao meio em O(2^(n/2) × n) de tempo, (2) aproximação gulosa para a variante fracionária ou (3) ramificação e poda. Na maioria dos problemas de entrevista com W <= 10⁵, a DP 1D com percurso para trás é a resposta esperada.

Quando W é muito grande, mas n é pequeno (por exemplo, n=40), a DP padrão O(nW) é inviável, mas a força bruta 2^n é lenta demais. A divisão ao meio separa os itens em duas metades, enumera todos os subconjuntos 2^(n/2) de cada metade e combina-os da melhor forma. Ordene uma metade por peso; depois, para cada subconjunto da outra metade, use busca binária para encontrar a melhor combinação dentro da capacidade. Isso leva O(2^(n/2) × n) — viável para n de até 40.

Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.

Nesta lição, você aprendeu: a DP da mochila 0/1 tem o estado dp[i][c], que representa o valor máximo com i itens e capacidade c, a recorrência decide se cada item será ignorado ou escolhido e a otimização de espaço 1D percorre a capacidade da direita para a esquerda para evitar a contagem dupla dos itens. Em seguida, exploraremos a mochila ilimitada, na qual os itens podem ser reutilizados, e aplicaremos esse conceito à Troca de Moedas II.