---
title: "Problema da Mochila (Knapsack) em Rust"
url: "https://rustlang.com.br/algoritmos/knapsack/"
markdown_url: "https://rustlang.com.br/algoritmos/knapsack.MD"
description: "Implemente o problema da mochila 0/1 em Rust com programação dinâmica: tabulação, memoização, backtracking de itens e variante fracionária."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# Problema da Mochila (Knapsack) em Rust

Implemente o problema da mochila 0/1 em Rust com programação dinâmica: tabulação, memoização, backtracking de itens e variante fracionária.


O **problema da mochila** (Knapsack) é um dos problemas mais estudados em otimização combinatória e ciência da computação. Dado um conjunto de itens, cada um com peso e valor, determine a combinação que maximiza o valor total sem exceder a capacidade da mochila. Aparece em alocação de recursos, carregamento de contêineres, seleção de portfólio de investimentos e até em compiladores (alocação de registradores).

Nesta página, implementamos a versão **0/1** (cada item é incluído ou excluído inteiramente) usando programação dinâmica em Rust, com visualização da tabela DP, reconstrução dos itens selecionados e comparação com a variante fracionária (gulosa).

## O Problema

**Entrada**: `n` itens, cada um com peso `w[i]` e valor `v[i]`, e uma capacidade máxima `W`.

**Objetivo**: Maximizar a soma dos valores dos itens selecionados, sem que a soma dos pesos ultrapasse `W`. Cada item pode ser incluído no máximo uma vez (0/1).

**Exemplo:**

```
Capacidade da mochila: W = 7

Itens:
  Item  | Peso | Valor
  ------|------|------
  A     |  1   |  1
  B     |  3   |  4
  C     |  4   |  5
  D     |  5   |  7

Solução ótima: itens B + C (peso = 3+4 = 7, valor = 4+5 = 9)
```

## Abordagem Ingênua (Força Bruta)

Testamos todas as 2^n combinações possíveis de itens:

```rust
/// Força bruta: testa todos os subconjuntos possíveis.
/// Complexidade: O(2^n) — impraticável para n > ~25.
fn knapsack_bruta(pesos: &[u32], valores: &[u32], capacidade: u32) -> u32 {
    fn resolver(pesos: &[u32], valores: &[u32], capacidade: u32, i: usize) -> u32 {
        // Caso base: sem itens ou sem capacidade
        if i == 0 || capacidade == 0 {
            return 0;
        }

        // Se o item atual não cabe, pule-o
        if pesos[i - 1] > capacidade {
            return resolver(pesos, valores, capacidade, i - 1);
        }

        // Máximo entre incluir ou não incluir o item
        let sem_item = resolver(pesos, valores, capacidade, i - 1);
        let com_item = valores[i - 1]
            + resolver(pesos, valores, capacidade - pesos[i - 1], i - 1);

        sem_item.max(com_item)
    }

    resolver(pesos, valores, capacidade, pesos.len())
}

fn main() {
    let pesos = [1, 3, 4, 5];
    let valores = [1, 4, 5, 7];
    let capacidade = 7;

    println!("Valor máximo: {}", knapsack_bruta(&pesos, &valores, capacidade));
    // Valor máximo: 9
}
```

O problema é que muitas chamadas com os mesmos parâmetros `(i, capacidade)` são repetidas, gerando trabalho redundante exponencial.

## Identificando Subestrutura Ótima

Para o item `i`, temos duas escolhas:
1. **Não incluir** o item `i`: o valor ótimo é `dp[i-1][w]`
2. **Incluir** o item `i` (se couber): o valor ótimo é `v[i] + dp[i-1][w - peso[i]]`

A recorrência é:

```
dp[i][w] = max(dp[i-1][w], v[i] + dp[i-1][w - peso[i]])   se peso[i] <= w
dp[i][w] = dp[i-1][w]                                       se peso[i] > w
```

Isso satisfaz ambas as condições de DP:
- **Subestrutura ótima**: a solução ótima para `i` itens com capacidade `w` depende de soluções ótimas para `i-1` itens.
- **Subproblemas sobrepostos**: o mesmo par `(i, w)` pode ser acessado por múltiplos caminhos de recursão.

## Visualização da Tabela DP

Para o exemplo com itens A(1,1), B(3,4), C(4,5), D(5,7) e capacidade 7:

```
             Capacidade w -->
             0   1   2   3   4   5   6   7
           +---+---+---+---+---+---+---+---+
  0 itens  | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
           +---+---+---+---+---+---+---+---+
  A (1,1)  | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
           +---+---+---+---+---+---+---+---+
  B (3,4)  | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
           +---+---+---+---+---+---+---+---+
  C (4,5)  | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
           +---+---+---+---+---+---+---+---+---+
  D (5,7)  | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
           +---+---+---+---+---+---+---+---+

Preenchimento (linha C, w=7):
  Sem C: dp[B][7] = 5
  Com C: valor_C + dp[B][7-4] = 5 + dp[B][3] = 5 + 4 = 9
  dp[C][7] = max(5, 9) = 9  <-- solução ótima!
```

## Complexidade

| Abordagem | Tempo | Espaço | Observação |
|-----------|-------|--------|------------|
| Força Bruta | O(2^n) | O(n) pilha | Impraticável para n > 25 |
| Top-Down (Memoização) | O(n * W) | O(n * W) | Pseudo-polinomial |
| Bottom-Up (Tabulação) | O(n * W) | O(n * W) | Iterativo |
| Otimizado (1 linha) | O(n * W) | O(W) | Percorre capacidades de trás para frente |

**Nota**: a complexidade é **pseudo-polinomial** porque `W` pode ser exponencialmente grande em relação ao tamanho da entrada em bits.

## Implementação: Top-Down (Memoização)

```rust
use std::collections::HashMap;

/// Mochila 0/1 com memoização usando HashMap.
/// Chave: (índice do item, capacidade restante).
fn knapsack_memo(
    pesos: &[u32],
    valores: &[u32],
    capacidade: u32,
    i: usize,
    cache: &mut HashMap<(usize, u32), u32>,
) -> u32 {
    // Caso base
    if i == 0 || capacidade == 0 {
        return 0;
    }

    // Verifica cache
    if let Some(&valor) = cache.get(&(i, capacidade)) {
        return valor;
    }

    let resultado = if pesos[i - 1] > capacidade {
        // Item não cabe — pula
        knapsack_memo(pesos, valores, capacidade, i - 1, cache)
    } else {
        // Melhor entre incluir ou não
        let sem = knapsack_memo(pesos, valores, capacidade, i - 1, cache);
        let com = valores[i - 1]
            + knapsack_memo(pesos, valores, capacidade - pesos[i - 1], i - 1, cache);
        sem.max(com)
    };

    cache.insert((i, capacidade), resultado);
    resultado
}

fn main() {
    let pesos = vec![1, 3, 4, 5];
    let valores = vec![1, 4, 5, 7];
    let capacidade = 7;
    let n = pesos.len();

    let mut cache = HashMap::new();
    let resultado = knapsack_memo(&pesos, &valores, capacidade, n, &mut cache);
    println!("Valor máximo (memoização): {}", resultado); // 9
}
```

## Implementação: Bottom-Up (Tabulação)

```rust
/// Mochila 0/1 com tabulação bottom-up.
/// Retorna o valor máximo E a tabela DP (para reconstrução).
fn knapsack_tabular(pesos: &[u32], valores: &[u32], capacidade: usize) -> (u32, Vec<Vec<u32>>) {
    let n = pesos.len();

    // dp[i][w] = valor máximo usando os primeiros i itens com capacidade w
    let mut dp = vec![vec![0u32; capacidade + 1]; n + 1];

    for i in 1..=n {
        for w in 0..=capacidade {
            // Opção 1: não incluir o item i
            dp[i][w] = dp[i - 1][w];

            // Opção 2: incluir o item i (se couber)
            let peso_item = pesos[i - 1] as usize;
            if peso_item <= w {
                let com_item = valores[i - 1] + dp[i - 1][w - peso_item];
                dp[i][w] = dp[i][w].max(com_item);
            }
        }
    }

    let valor_maximo = dp[n][capacidade];
    (valor_maximo, dp)
}

fn main() {
    let pesos = vec![1, 3, 4, 5];
    let valores = vec![1, 4, 5, 7];
    let nomes = vec!["A", "B", "C", "D"];
    let capacidade = 7;

    let (valor, _dp) = knapsack_tabular(&pesos, &valores, capacidade);
    println!("Valor máximo (tabulação): {}", valor); // 9
}
```

## Otimização de Espaço

Como cada linha `i` depende apenas da linha `i-1`, podemos usar um único vetor, percorrendo as capacidades **de trás para frente** para evitar sobrescrever valores ainda necessários:

```rust
/// Mochila 0/1 otimizada: O(n*W) tempo, O(W) espaço.
fn knapsack_otimizado(pesos: &[u32], valores: &[u32], capacidade: usize) -> u32 {
    let n = pesos.len();
    let mut dp = vec![0u32; capacidade + 1];

    for i in 0..n {
        // IMPORTANTE: percorrer de trás para frente!
        // Se percorrermos para frente, usaríamos valores já atualizados
        // desta linha, o que equivaleria a mochila ilimitada.
        for w in (pesos[i] as usize..=capacidade).rev() {
            let com_item = valores[i] + dp[w - pesos[i] as usize];
            dp[w] = dp[w].max(com_item);
        }
    }

    dp[capacidade]
}

fn main() {
    let pesos = vec![1, 3, 4, 5];
    let valores = vec![1, 4, 5, 7];
    let capacidade = 7;

    println!("Valor máximo (otimizado): {}", knapsack_otimizado(&pesos, &valores, capacidade));
    // 9
}
```

## Reconstruindo a Solução

Para saber **quais itens** foram selecionados, percorremos a tabela DP de volta:

```rust
/// Reconstrói quais itens foram selecionados a partir da tabela DP.
fn reconstruir_itens(dp: &[Vec<u32>], pesos: &[u32], capacidade: usize) -> Vec<usize> {
    let n = dp.len() - 1;
    let mut itens_selecionados = Vec::new();
    let mut w = capacidade;

    for i in (1..=n).rev() {
        // Se dp[i][w] != dp[i-1][w], o item i foi incluído
        if dp[i][w] != dp[i - 1][w] {
            itens_selecionados.push(i - 1); // índice 0-based
            w -= pesos[i - 1] as usize;
        }
    }

    itens_selecionados.reverse();
    itens_selecionados
}

fn main() {
    let pesos = vec![1, 3, 4, 5];
    let valores = vec![1, 4, 5, 7];
    let nomes = vec!["A", "B", "C", "D"];
    let capacidade: usize = 7;

    let (valor, dp) = knapsack_tabular(&pesos, &valores, capacidade);
    let itens = reconstruir_itens(&dp, &pesos, capacidade);

    println!("Valor máximo: {}", valor);
    println!("Itens selecionados:");
    let mut peso_total = 0;
    for &idx in &itens {
        println!("  {} — peso: {}, valor: {}", nomes[idx], pesos[idx], valores[idx]);
        peso_total += pesos[idx];
    }
    println!("Peso total: {}/{}", peso_total, capacidade);
}

/// Mochila 0/1 com tabulação bottom-up (necessária para reconstrução).
fn knapsack_tabular(pesos: &[u32], valores: &[u32], capacidade: usize) -> (u32, Vec<Vec<u32>>) {
    let n = pesos.len();
    let mut dp = vec![vec![0u32; capacidade + 1]; n + 1];

    for i in 1..=n {
        for w in 0..=capacidade {
            dp[i][w] = dp[i - 1][w];
            let peso_item = pesos[i - 1] as usize;
            if peso_item <= w {
                let com_item = valores[i - 1] + dp[i - 1][w - peso_item];
                dp[i][w] = dp[i][w].max(com_item);
            }
        }
    }

    (dp[n][capacidade], dp)
}
```

### Variante: Mochila Fracionária (Gulosa)

Na versão fracionária, podemos pegar frações de itens. A solução ótima é **gulosa**: ordene por valor/peso e preencha.

```rust
/// Mochila fracionária: solução gulosa O(n log n).
/// Ao contrário da 0/1, aqui podemos pegar frações de itens.
fn knapsack_fracionaria(pesos: &[f64], valores: &[f64], capacidade: f64) -> f64 {
    let n = pesos.len();

    // Cria lista de índices ordenada por valor/peso (decrescente)
    let mut indices: Vec<usize> = (0..n).collect();
    indices.sort_by(|&a, &b| {
        let razao_a = valores[a] / pesos[a];
        let razao_b = valores[b] / pesos[b];
        razao_b.partial_cmp(&razao_a).unwrap()
    });

    let mut valor_total = 0.0;
    let mut capacidade_restante = capacidade;

    for &i in &indices {
        if capacidade_restante <= 0.0 {
            break;
        }

        if pesos[i] <= capacidade_restante {
            // Pega o item inteiro
            valor_total += valores[i];
            capacidade_restante -= pesos[i];
        } else {
            // Pega fração do item
            let fracao = capacidade_restante / pesos[i];
            valor_total += valores[i] * fracao;
            capacidade_restante = 0.0;
        }
    }

    valor_total
}

fn main() {
    let pesos = vec![1.0, 3.0, 4.0, 5.0];
    let valores = vec![1.0, 4.0, 5.0, 7.0];
    let capacidade = 7.0;

    let resultado = knapsack_fracionaria(&pesos, &valores, capacidade);
    println!("Valor máximo (fracionária): {:.2}", resultado);
    // Ordena por razão: D(1.40), B(1.33), C(1.25), A(1.00)
    // Pega D inteiro (peso 5, valor 7), fração 2/3 de B (peso 2, valor 2.67)
    // Total: 9.67
}
```

## Exercícios Práticos

1. **Mochila ilimitada**: Modifique a solução para permitir repetição de itens (cada item pode ser incluído quantas vezes quiser). Dica: percorra as capacidades da esquerda para a direita no vetor otimizado.

2. **Mochila com contagem**: Dado que existem `q[i]` cópias de cada item, encontre o valor máximo. Esta é a variante "bounded knapsack".

3. **Mochila com peso exato**: Encontre o valor máximo usando **exatamente** capacidade `W` (não "até W"). Dica: inicialize `dp` com valores negativos impossíveis, exceto `dp[0] = 0`.

4. **Contar soluções**: Em vez do valor máximo, conte quantas combinações distintas de itens somam exatamente peso `W`.

## Veja Também

- [Vec — Vetores dinâmicos](/stdlib/vec/) — base para a tabela DP bidimensional
- [Arrays — Tamanho fixo](/stdlib/arrays/) — alternativa quando dimensões são conhecidas em tempo de compilação
- [Eq e Ord — Comparação e ordenação](/stdlib/eq-ord/) — traits usados na ordenação por razão valor/peso
- [Fibonacci com DP](/algoritmos/fibonacci-dp/) --- introdução a programação dinâmica
- [Soma de Subconjuntos](/algoritmos/subset-sum/) --- variante decisional da mochila
- [Troco de Moedas](/algoritmos/coin-change/) --- variante com mochila ilimitada