Published

22/04/2026

Modified

22/04/2026

O Problema da Mochila (Knapsack 0-1)

Metáfora e Motivação

O problema mais clássico de Programação Dinâmica talvez seja o Knapsack, ou o Problema da Mochila. De maneira geral, um ladrão irá roubar uma casa carregando uma mochila que suporta um peso máximo estrito \(S\). Ele vê \(N\) objetos na casa e sabe estimar o peso \(P_i\) e o valor \(V_i\) de cada objeto \(i\).

Pergunta de um milhão de dólares: Qual o maior valor que o ladrão pode roubar sem rasgar a mochila?

A Derrota dos Algoritmos Gulosos

Como vimos nas aulas de Gulosos, se a mochila for fracionária (divisível), ordenar pela proporção Valor / Peso resolve o problema. Se for inteira/binária (0-1), o guloso comete atrocidades:

  • Mochila: Suporta 12 Kg
  • Objeto A: Peso 10 Kg | Valor 9
  • Objeto B: Peso 6 Kg | Valor 5
  • Objeto C: Peso 6 Kg | Valor 5

Um algoritmo guloso tentaria pegar o Objeto A (maior valor ou maior densidade) e entupiria a mochila, faturando 9. Sobrariam 2 Kg que não cabem mais nada. A resposta otimizada? Ignorar o A, e pegar o B e o C! Juntos faturariam 10 (\(5 + 5\)) ocupando exatos 12 Kg (\(6 + 6\)).

O Raciocínio Top-Down (Pegar ou Largar)

Para resolver o impasse com Programação Dinâmica (DP), basta observar um objeto e decidir bifurcar o universo criando duas simulações paralelas exaustivas perfeitamente mapeadas.

Dado um Objeto i, nosso estado na tabela será regido por 2 variáveis: dp(índice_objeto, espaço_restante). 1. Universo 1 (Não Coloquei na Mochila): O espaço na mochila continua intacto. Passo para o próximo objeto ileso. 2. Universo 2 (Coloquei na Mochila): Ganho o valor daquele objeto somado na minha carteira mágica, e subtraio o peso dele do espaço restante da mochila nas próximas instâncias. Só posso entrar nesse universo se a mochila suportar o respectivo pedágio (peso do objeto \(\le\) espaço restante)!

Ao final comparo o universo 1 e 2, e escolho qual me retornou a maior conta bancária.

Árvore de Estado DP (Mermaid)

Veja como uma mochila de Espaço = 10 tentando decidir sobre o primeiro item pesado Item(peso=8, valor=5) quebra a matriz:

O Coração da DP: Memoização

Como testamos todo o subespaço com esse formato de decisão binária em árvore, no total teríamos \(\mathcal{O}(2^N)\) e explodiríamos o servidor do juiz. Felizmente a subestrutura é repetida. Ao usarmos uma matriz salva em cache chamada tab[obj][aguenta] = melhor_caminho_ja_calculado, achatamos a nossa força bruta complexa para esplêndidos \(\mathcal{O}(N \times S)\).

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cassert>

using namespace std;

// Constantes amigaveis de espaço para matriz da DP Global
const int MAX_OBJETOS = 100;
const int MAX_CAPACIDADE = 1000;

int N; // Quantidade total de Objetos no experimento Global 
int tabela[MAX_OBJETOS][MAX_CAPACIDADE];
vector<int> pesos;
vector<int> valores;

int knapsack(int obj, int aguenta) {
    // 1. Caso Base: Se não tem mais objetos na prateleira ou não cabe um ácaro 
    if(obj == N || aguenta == 0) {
        return 0;
    }
    
    // 2. Transição de Ouro (Memoização): Esse cenário numérico de colisão espacial / obj já foi pesquisado!?
    if(tabela[obj][aguenta] != -1) {
        return tabela[obj][aguenta];
    }
    
    // 3. Simulação - Universo Alternativo: Ignoro o peso atual
    int nao_coloca = knapsack(obj + 1, aguenta);
    int coloca = -1; // Flag inútil caso não valha a pena / não caiba
    
    // Simulação 2: Quero colocar
    if(pesos[obj] <= aguenta) {
        coloca = valores[obj] + knapsack(obj + 1, aguenta - pesos[obj]);
    }
    
    // 4. Fecho do Fluxo: Avalia e Salva. Qual universodeu mais lucro?
    return tabela[obj][aguenta] = max(nao_coloca, coloca);
}

void executando_testes() {
    // Modelo exposto inicialmente no texto (12Kg vs 3 itens)
    N = 3;
    int capacidade_Mochila = 12;
    pesos = {10, 6, 6};
    valores = {9, 5, 5};
    
    // Sempre resetamos toda a tabela com lixo -1 antes de disparar top-down memorizada para competições
    memset(tabela, -1, sizeof(tabela));
    
    // Rodando o Motor no Teto (Item do Indice 0, Teto peso da Mochila 12)
    int maxLucro = knapsack(0, capacidade_Mochila);
    
    // Provamos fisicamente que ele pega os itens de 5 e 5 matando o Guloso cego
    assert(maxLucro == 10);
    
    cout << "[✅] Testes Dinâmicos da Mochila binária (0-1) validados!\n";
}

int main() {
    executando_testes();
    return 0;
}

A complexidade despenca drasticamente, pois a máquina iterará fisicamente e computará com suas próprias mãos matemáticas a equação do corpo condicional no máximo \(N \times S\) vezes.

Exercício Guiado: Transição para o Mundo Bottom-Up

O código acima escrevemos numa abordagem Top-Down (começamos do fim pedindo para recursão resolver as ramificações baixas). Tente desenhar o esqueleto forçando loopings duplos de forma matricial (Bottom-Up). No Beecrowd, como os problemas estouram rapidamente a pilha recursiva do compilador e limites de memória temporal limitados, Bottom-Up acaba oferecendo micro-segundos absolutos de salvação, além da possibilidade mágica de reduzir tab[MAX_OBJ][MAX_CAPACIDADE] em tab[MAX_CAPACIDADE] jogando uma dimensão inteira fora economizando gigabytes.

Exercícios Sugeridos

Problemas de maratonas sobre Seleções de Itens com escassez de custo / peso (Válvula clássica das Mochilas!):

Back to top