Problema da Mochila
Maximiza o valor total de itens em uma mochila com capacidade limitada — preenchendo uma tabela de subproblemas de baixo para cima.
O(n·m)O(n·m)Como Funciona
Passo a passo do algoritmo
Definição do subproblema
dp[i][w] representa o valor máximo que podemos obter usando os i primeiros itens com uma capacidade de exatamente w. Ao decompor o problema original em subproblemas menores, resolvemos cada um apenas uma vez.
dp[i][w] = max valor usando itens 1..i com capacidade wCaso base
dp[0][w] = 0 para todo w (nenhum item disponível → valor 0). dp[i][0] = 0 para todo i (capacidade zero → nada cabe). Toda a tabela começa preenchida com zeros.
dp[0][w] = 0 ∀w; dp[i][0] = 0 ∀iRecorrência: incluir ou não incluir
Para cada item i com peso pᵢ e valor vᵢ, e para cada capacidade w: se o item não cabe (pᵢ > w), mantemos o valor anterior dp[i-1][w]. Caso contrário, escolhemos o maior entre não incluir e incluir.
se pᵢ > w: dp[i][w] = dp[i-1][w]
senão: dp[i][w] = max(dp[i-1][w], vᵢ + dp[i-1][w-pᵢ])Preenchimento bottom-up
Preenchemos a tabela linha por linha (item por item) e coluna por coluna (capacidade crescente). Cada célula depende apenas de valores da linha anterior, garantindo que todos os subproblemas estejam resolvidos antes de serem usados.
para i de 1 até n: para w de 0 até W: calcular dp[i][w]Rastreamento da solução
Após preencher a tabela, percorremos de volta: se dp[i][w] ≠ dp[i-1][w], o item i foi incluído, subtraímos seu peso de w e seguimos para i-1. Caso contrário, o item não foi usado.
i=n, w=W; se dp[i][w] ≠ dp[i-1][w]: incluir item i; w -= pᵢ; i--Implementação
Código comentado em JavaScript e Python
function mochila(itens, capacidade) {
const n = itens.length;
// Tabela dp[i][w]: valor max com i primeiros itens e capacidade w
const dp = Array.from({ length: n + 1 }, () =>
new Array(capacidade + 1).fill(0)
);
// Preencher bottom-up
for (let i = 1; i <= n; i++) {
const { peso, valor } = itens[i - 1];
for (let w = 0; w <= capacidade; w++) {
if (peso > w) {
dp[i][w] = dp[i - 1][w]; // item não cabe
} else {
dp[i][w] = Math.max(
dp[i - 1][w], // não incluir
valor + dp[i - 1][w - peso] // incluir
);
}
}
}
// Rastrear itens escolhidos
const escolhidos = [];
let w = capacidade;
for (let i = n; i > 0; i--) {
if (dp[i][w] !== dp[i - 1][w]) {
escolhidos.push(itens[i - 1]);
w -= itens[i - 1].peso;
}
}
return { valorMaximo: dp[n][capacidade], itens: escolhidos };
}
// Exemplo
const itens = [
{ nome: 'Câmera', peso: 1, valor: 3 },
{ nome: 'Livro', peso: 2, valor: 4 },
{ nome: 'Laptop', peso: 3, valor: 5 },
{ nome: 'Tablet', peso: 4, valor: 6 }
];
const resultado = mochila(itens, 5);
console.log('Valor máximo:', resultado.valorMaximo); // 8
console.log('Itens:', resultado.itens.map(i => i.nome)); // ['Câmera', 'Laptop']Playground
Visualize o algoritmo em ação
| cap → | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| — | 0 | 0 | 0 | 0 | 0 | 0 |
| Câme | 0 | 0 | 0 | 0 | 0 | 0 |
| Livr | 0 | 0 | 0 | 0 | 0 | 0 |
| Lapt | 0 | 0 | 0 | 0 | 0 | 0 |
| Tabl | 0 | 0 | 0 | 0 | 0 | 0 |
Quando Usar
Cenários ideais para este algoritmo
Logística e transporte
Selecionar quais cargas transportar em um veículo de capacidade limitada maximizando o valor entregue.
Finanças e portfólio
Selecionar investimentos com retorno máximo dentro de um orçamento — cada ativo tem custo e retorno esperado.
Alocação de recursos
Distribuir memória, tempo de CPU ou banda entre tarefas com diferentes requisitos e benefícios.
Corte de materiais
Definir como cortar matéria-prima (madeira, tecido) para maximizar o aproveitamento e minimizar desperdício.
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Preenchimento da tabela | O(n·W) |
| Rastreamento da solução | O(n) |
| Capacidade W grande | O(n·W) |