Equipe Rust Brasil 9 min de leitura

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.

programação dinâmica knapsack mochila otimização rust

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:

/// 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

AbordagemTempoEspaçoObservação
Força BrutaO(2^n)O(n) pilhaImpraticá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)

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)

/// 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:

/// 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:

/// 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.

/// 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