Numexa logoNumexa

Problema da Mochila 0/1

Programação dinâmica com a tabela completa e explicação de cada célula.

ItemPesoValor
Valor máximo: 5.300 levando Notebook, Câmera, Celular (peso total 5 de 5).
item \ capacidade012345
nenhum000000
1. Notebook000200020002000
2. Câmera015001500200035003500
3. Violão015001500200035004500
4. Celular018003300330038005300

Clique em uma célula da tabela para ver como ela foi calculada. Em verde, o caminho de volta que define os itens escolhidos.

O problema da mochila (knapsack problem) é o exemplo clássico de programação dinâmica. A ferramenta monta a tabela inteira, destaca o caminho que define os itens escolhidos e explica o cálculo de qualquer célula em que você clicar.

Fórmula de Recorrência

dp[0][w] = 0

dp[i][w] = dp[i-1][w]                                    se peso[i] > w
dp[i][w] = max(dp[i-1][w], dp[i-1][w - peso[i]] + valor[i])   caso contrário

Em Python

def mochila(pesos, valores, capacidade):
    n = len(pesos)
    dp = [[0] * (capacidade + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacidade + 1):
            dp[i][w] = dp[i - 1][w]
            if pesos[i - 1] <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - pesos[i - 1]] + valores[i - 1])
    return dp[n][capacidade]

Versão com Uma Linha (Menos Memória)

int mochila(int n, int W, int peso[], int valor[]) {
    int dp[W + 1];
    for (int w = 0; w <= W; w++) dp[w] = 0;
    for (int i = 0; i < n; i++)
        for (int w = W; w >= peso[i]; w--)       /* de trás para frente! */
            if (dp[w - peso[i]] + valor[i] > dp[w])
                dp[w] = dp[w - peso[i]] + valor[i];
    return dp[W];
}

Percorrer a capacidade de trás para frente garante que cada item seja usado no máximo uma vez. Se percorrer de frente para trás, o mesmo código resolve a mochila ilimitada, em que cada item pode ser levado várias vezes.

Onde Aparece na Prática

  • Escolha de investimentos com orçamento limitado.
  • Corte de materiais e carregamento de caminhões e contêineres.
  • Alocação de recursos em computação em nuvem.
  • Criptografia: os primeiros sistemas de chave pública (Merkle-Hellman) usavam uma variante do problema.

Perguntas Frequentes

O que é o problema da mochila?

Dado um conjunto de itens, cada um com peso e valor, e uma mochila com capacidade máxima, escolher quais itens levar para maximizar o valor total sem passar do peso. Na versão 0/1, cada item é levado inteiro ou não é levado.

Por que o algoritmo guloso não funciona?

Escolher sempre o item de maior valor pode deixar espaço mal aproveitado. No exemplo carregado (capacidade 5), o guloso pega primeiro o violão (peso 4, valor 3.000) e depois o celular, somando 4.800. A programação dinâmica encontra notebook + câmera + celular, que somam 5.300 com o mesmo peso. Só a programação dinâmica garante o ótimo.

Como funciona a tabela da programação dinâmica?

A célula dp[i][w] guarda o melhor valor usando só os primeiros i itens e capacidade w. Ela é o maior entre não levar o item i (dp[i−1][w]) e levá-lo (dp[i−1][w − peso] + valor). A resposta final fica na última célula.

Qual a complexidade do problema da mochila?

A programação dinâmica roda em O(n·W), com n itens e capacidade W. Isso é pseudo-polinomial: cresce com o valor da capacidade, não com o número de dígitos dela. O problema da mochila é NP-difícil no caso geral.

Ferramentas Relacionadas