8 min
← Voltar
1
0 XP

0/1 Knapsack

Dada uma lista de itens com peso e valor, e uma mochila com capacidade limitada, escolha quais itens levar para maximizar o valor total. Cada item só pode ser pego uma vez.

MédiaO(n × W) / O(n × W)DP2DOtimizaçãoMochilaBacktrack

Visualizador Interativo

Pensamento DP

Como pensar em 0/1 Knapsack como DP

etapa 1 / 5
◇

Identificar Estado

Pergunta-guia“Quais informações eu preciso lembrar para resolver um subproblema?”

Diferente do Coin Change (1 dimensão), aqui temos dois eixos de variação: quais itens já considerei e quanta capacidade ainda tenho na mochila. Os dois precisam estar no estado.

Indexamos linhas pelos itens (0 = nenhum item, n = todos) e colunas pela capacidade restante (0 a W). Cada célula guarda o melhor valor possível dentro desses limites.

dp[i][w] = melhor valor usando apenas os primeiros i itens com capacidade w
Vira em códigopython
1def knapsack(weights, values, capacity):
2 n = len(weights)
3dp = [[0] * (capacity + 1) for _ in range(n + 1)]
Capacidade7kg
Passo 1 / 34
Itens disponíveis
💎
Joia
4kg$3
📚
Livro
2kg$4
💻
Laptop
3kg$5
Tabela dp[i][w]
0
1
2
3
4
5
6
7
∅
0
0
0
0
0
0
0
0
💎
0
0
0
0
0
0
0
0
📚
0
0
0
0
0
0
0
0
💻
0
0
0
0
0
0
0
0
dp inicializado em zeros. Cada célula dp[i][w] guarda o melhor valor usando os primeiros i itens com capacidade w.
Mochila
peso0/7
valor$0
Velocidade:1000ms
Historico de Passos
#0Tabela 4×8 zerada. Linha 0 (sem itens) e coluna 0 (sem capacidade) ficam em zero.

Como Funciona

O problema da mochila 0/1 é um dos exemplos canônicos de DP em duas dimensões. Em cada célula dp[i][w], guardamos o melhor valor possível usando apenas os primeiros i itens com capacidade w disponível. Para cada item i e capacidade w, fazemos uma decisão binária: - skip: dp[i-1][w] (ignora o item) - take: dp[i-1][w - weight[i]] + value[i] (pega o item, se couber) A recorrência: dp[i][w] = max(skip, take). Construímos a tabela de cima pra baixo, da esquerda pra direita. Quando chegamos em dp[n][W], temos a resposta. Para descobrir QUAIS itens foram escolhidos, percorremos a tabela de volta: se dp[i][w] ≠ dp[i-1][w], o item i entrou na solução, então subtraímos seu peso e seguimos. A versão fracionária (Fractional Knapsack) tem solução gulosa O(n log n), mas a 0/1 não — daí a necessidade de DP.

“A "ordem dos itens" no array não importa para o valor final, mas a indexação por linha permite a recorrência. dp[i][w] sempre olha para a linha anterior — isso permite até reduzir espaço para O(W) com cuidado.”

Passo a Passo

  1. Inicializa dp[0][*] = 0 e dp[*][0] = 0
  2. Para cada item i de 1 até n
  3. Para cada capacidade w de 0 até W
  4. Se peso[i] > w, copia dp[i-1][w] (não cabe)
  5. Caso contrário, dp[i][w] = max(skip, take)
  6. Faz backtrack a partir de dp[n][W] para reconstruir os itens escolhidos

Análise de Complexidade

⏱️Tempo
O(n × W)

n itens × W+1 capacidades. Cada célula é computada em O(1).

Ver prova

Tabela tem (n+1) × (W+1) células, cada uma O(1) → O(n × W)

💾Espaco
O(n × W)

Tabela 2D completa. Pode ser reduzida a O(W) iterando capacidade decrescente.

🎯Melhor Caso
O(n × W)

DP sempre preenche toda a tabela.

⚠️Pior Caso
O(n × W)

Mesma complexidade em qualquer entrada — independente dos valores.

Comparação com Outros Algoritmos

AlgoritmoTempoEspacoMelhor Para
0/1 Knapsack (DP)(atual)O(n × W)O(n × W)Capacidade pequena/moderada, itens indivisíveis
Fractional Knapsack (Guloso)O(n log n)O(1)Quando itens podem ser fracionados (ouro em pó, líquidos)
0/1 Knapsack (Branch & Bound)Exponencial pior casoO(n)Capacidade muito grande (W pseudo-polinomial)

Dicas e Erros Comuns

  • Confundir índice base 0 dos arrays com índice 1-based do dp (peso[i-1] no Python)
  • Esquecer de checar se o peso cabe antes de calcular o valor "take"
  • Misturar 0/1 (cada item uma vez) com Unbounded Knapsack (uso ilimitado)
  • Tentar reduzir para O(W) sem inverter o loop interno — quebra a invariante

Perguntas de Entrevista

Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.

Implementacao

python
1def knapsack(weights, values, capacity):Definição
2    n = len(weights)
3    dp = [[0] * (capacity + 1) for _ in range(n + 1)]Inicialização do DP
4 
5    for i in range(1, n + 1):Loop de Itens
6        for w in range(capacity + 1):Loop de Capacidades
7            if weights[i - 1] > w:Cabe na mochila?
8                dp[i][w] = dp[i - 1][w]
9            else:
10                skip = dp[i - 1][w]
11                take = dp[i - 1][w - weights[i - 1]] + values[i - 1]
12                dp[i][w] = max(skip, take)Decisão Take vs Skip
13 
14    # Backtrack para reconstruir os itens
15    chosen = []Backtrack
16    i, w = n, capacity
17    while i > 0:
18        if dp[i][w] != dp[i - 1][w]:
19            chosen.append(i - 1)
20            w -= weights[i - 1]
21        i -= 1
22 
23    return dp[n][capacity], list(reversed(chosen))
24