Mochila com Espaço Otimizado

Uma tabela completa consome n vezes cap de memória, o que pode explodir com entradas grandes. A otimização de espaço reduz isso a uma única linha reutilizada.

Observe que cada célula lê apenas a linha anterior, nunca algo mais antigo. Portanto, você não precisa armazenar toda a grade de uma vez.

Mantenha um vetor dp de comprimento cap+1. Ao processar cada item, atualize-o no próprio lugar para representar a nova linha.

Se você percorrer a capacidade da esquerda para a direita, dp[w - wt[i]] talvez já tenha sido atualizado para este mesmo item. Isso permitiria pegar o item i duas vezes.

A solução é percorrer a capacidade do maior valor para o menor. Ir para trás garante que dp[w - wt[i]] ainda contenha o valor do item anterior.

Ao calcular dp[w], o índice menor w - wt[i] ainda não foi alterado nesta rodada, portanto reflete a linha anterior como desejado.

Capacidades menores que wt[i] não comportam o item, então o laço para em wt[i]. Ignorá-las economiza algumas iterações inofensivas.

A solução inteira consiste em dois laços aninhados sobre um vetor. Itens por fora, capacidade para trás por dentro, e a resposta surge.

Depois de todos os itens, dp[cap] contém o valor máximo. É o mesmo número que a tabela 2D forneceria, usando muito menos memória.

Você não acelerou o algoritmo; ele ainda executa trabalho da ordem de n vezes cap. Você apenas reduziu a memória de quadrática para linear.

Esse truque ajuda quando cap é grande e a grade 2D ultrapassaria o limite de memória. É um clássico das competições que vale a pena memorizar.

Teste a regra principal da mochila 1D.

Você reduziu a tabela 2D a um vetor e percorreu a capacidade para trás para manter a correção, trocando memória quadrática por linear. 🚀