Equipe Rust Brasil 11 min de leitura

Problema do Troco de Moedas em Rust

Resolva o problema do troco de moedas em Rust com programação dinâmica: mínimo de moedas, contagem de formas e relação com mochila ilimitada.

programação dinâmica troco moedas otimização rust

O problema do troco de moedas é um clássico de programação dinâmica com aplicação direta no mundo real: dado um conjunto de denominações de moedas e um valor alvo, qual o número mínimo de moedas necessárias para atingir exatamente esse valor? Esse problema aparece em caixas eletrônicos, sistemas de pagamento, alocação de recursos e como base para entender a mochila ilimitada (unbounded knapsack).

Nesta página, implementamos duas variantes em Rust: mínimo de moedas (otimização) e contagem de formas (combinatória), com visualizações do array DP e análise completa.

O Problema

Variante 1: Mínimo de Moedas

Entrada: Um conjunto de denominações moedas[] e um valor alvo.

Objetivo: Encontrar o número mínimo de moedas que somam exatamente alvo. Cada denominação pode ser usada quantas vezes quiser. Se for impossível, retornar -1.

Variante 2: Contagem de Formas

Objetivo: Contar de quantas maneiras distintas podemos formar o valor alvo.

Exemplo:

Moedas: [1, 5, 10, 25]
Alvo: 30

Variante 1 (mínimo): 2 moedas (25 + 5)
Variante 2 (formas): diversas combinações:
  30x1, 25x1+5x1, 25x1+5x1, 20x1+10x1, ...

Abordagem Ingênua (Força Bruta)

Tentamos todas as combinações recursivamente:

/// Força bruta: testa todas as combinações de moedas.
/// Complexidade: O(n^(alvo/menor_moeda)) — exponencial.
fn troco_bruta(moedas: &[u32], alvo: u32) -> i32 {
    if alvo == 0 {
        return 0;
    }

    let mut melhor = i32::MAX;

    for &moeda in moedas {
        if moeda <= alvo {
            let resultado = troco_bruta(moedas, alvo - moeda);
            if resultado >= 0 && resultado + 1 < melhor {
                melhor = resultado + 1;
            }
        }
    }

    if melhor == i32::MAX { -1 } else { melhor }
}

fn main() {
    let moedas = [1, 5, 10, 25];
    let alvo = 30;
    println!("Mínimo de moedas: {}", troco_bruta(&moedas, alvo)); // 2
}

O problema é que o mesmo valor intermediário é recalculado inúmeras vezes. Por exemplo, para alcançar o valor 15, a recursão pode chegar a ele por 25 -> 15, 10 + 5 -> 15, 10 + 1*5 -> 15, etc.

Identificando Subestrutura Ótima

Para o mínimo de moedas:

dp[v] = número mínimo de moedas para formar o valor v

dp[0] = 0  (zero moedas para valor zero)
dp[v] = min(dp[v - moeda] + 1) para cada moeda <= v

Para a contagem de formas:

dp[v] = número de formas de formar o valor v

dp[0] = 1  (uma forma: não usar nenhuma moeda)
Para cada moeda c:
    dp[v] += dp[v - c]  para v >= c

Ambas as variantes satisfazem:

  • Subestrutura ótima: a solução ótima para v se constrói a partir de soluções para v - moeda.
  • Subproblemas sobrepostos: o mesmo valor intermediário é acessado múltiplas vezes.

Relação com mochila ilimitada: o troco de moedas é essencialmente uma mochila ilimitada onde os “pesos” são as denominações e o objetivo é minimizar o número de itens (ou contar combinações).

Visualização da Tabela DP

Para moedas [1, 3, 4] e alvo 6 (mínimo de moedas):

Valor:     0   1   2   3   4   5   6
         +---+---+---+---+---+---+---+
dp:      | 0 | INF INF INF INF INF INF|  (inicialização)
         +---+---+---+---+---+---+---+

Processando moeda = 1:
dp:      | 0 | 1 | 2 | 3 | 4 | 5 | 6 |

Processando moeda = 3:
  dp[3] = min(dp[3], dp[3-3]+1) = min(3, 0+1) = 1
  dp[4] = min(dp[4], dp[4-3]+1) = min(4, 1+1) = 2
  dp[5] = min(dp[5], dp[5-3]+1) = min(5, 2+1) = 3
  dp[6] = min(dp[6], dp[6-3]+1) = min(6, 3+1) = 2  (duas moedas de 3!)
dp:      | 0 | 1 | 2 | 1 | 2 | 3 | 2 |

Processando moeda = 4:
  dp[4] = min(dp[4], dp[4-4]+1) = min(2, 0+1) = 1
  dp[5] = min(dp[5], dp[5-4]+1) = min(3, 1+1) = 2
  dp[6] = min(dp[6], dp[6-4]+1) = min(2, 2+1) = 2
dp:      | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
                           ^           ^
                        1x moeda 4   mínimo: 2 moedas (3+3 ou 4+1+1)

Resultado: dp[6] = 2

Para a contagem de formas com moedas [1, 2, 5] e alvo 5:

Valor:        0   1   2   3   4   5
            +---+---+---+---+---+---+
Inicial:    | 1 | 0 | 0 | 0 | 0 | 0 |

Após moeda=1:| 1 | 1 | 1 | 1 | 1 | 1 |  (só com moedas de 1)

Após moeda=2:| 1 | 1 | 2 | 2 | 3 | 3 |  (com moedas de 1 e 2)

Após moeda=5:| 1 | 1 | 2 | 2 | 3 | 4 |  (com moedas de 1, 2 e 5)

Resultado: 4 formas de dar troco para 5:
  [1,1,1,1,1], [1,1,1,2], [1,2,2], [5]

Complexidade

AbordagemTempoEspaçoObservação
Força BrutaO(n^(V/min_c))O(V) pilhan = qtd moedas, V = alvo
Top-Down (Memoização)O(n * V)O(V) cachen = qtd moedas
Bottom-Up (Tabulação)O(n * V)O(V)Iterativo, vetor 1D
OtimizadoO(n * V)O(V)Já é a versão otimizada!

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

use std::collections::HashMap;

/// Mínimo de moedas com memoização.
fn troco_memo(moedas: &[u32], alvo: u32, cache: &mut HashMap<u32, i32>) -> i32 {
    // Caso base: valor zero requer zero moedas
    if alvo == 0 {
        return 0;
    }

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

    let mut melhor = i32::MAX;

    // Tenta cada denominação
    for &moeda in moedas {
        if moeda <= alvo {
            let sub = troco_memo(moedas, alvo - moeda, cache);
            if sub >= 0 && sub + 1 < melhor {
                melhor = sub + 1;
            }
        }
    }

    let resultado = if melhor == i32::MAX { -1 } else { melhor };
    cache.insert(alvo, resultado);
    resultado
}

fn main() {
    let moedas = vec![1, 5, 10, 25];
    let alvo = 30;

    let mut cache = HashMap::new();
    let resultado = troco_memo(&moedas, alvo, &mut cache);
    println!("Mínimo de moedas para {}: {}", alvo, resultado); // 2

    cache.clear();
    let alvo2 = 11;
    let moedas2 = vec![3, 5];
    let resultado2 = troco_memo(&moedas2, alvo2, &mut cache);
    println!("Mínimo para {} com {:?}: {}", alvo2, moedas2, resultado2); // 3 (5+3+3)

    cache.clear();
    let moedas3 = vec![2];
    let resultado3 = troco_memo(&moedas3, 3, &mut cache);
    println!("Mínimo para 3 com [2]: {}", resultado3); // -1 (impossível)
}

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

Variante 1: Mínimo de Moedas

/// Mínimo de moedas com tabulação bottom-up.
/// Retorna o número mínimo de moedas ou None se impossível.
fn troco_minimo(moedas: &[u32], alvo: usize) -> Option<usize> {
    // dp[v] = mínimo de moedas para formar o valor v
    // Usamos usize::MAX como "infinito" (impossível)
    let mut dp = vec![usize::MAX; alvo + 1];
    dp[0] = 0; // Caso base: zero moedas para valor zero

    for v in 1..=alvo {
        for &moeda in moedas {
            let c = moeda as usize;
            if c <= v && dp[v - c] != usize::MAX {
                dp[v] = dp[v].min(dp[v - c] + 1);
            }
        }
    }

    if dp[alvo] == usize::MAX {
        None
    } else {
        Some(dp[alvo])
    }
}

fn main() {
    let moedas = vec![1, 5, 10, 25];

    for alvo in [6, 11, 15, 30, 99] {
        match troco_minimo(&moedas, alvo) {
            Some(n) => println!("Troco para {}: {} moedas", alvo, n),
            None => println!("Troco para {}: impossível", alvo),
        }
    }
    // Troco para 6: 2 moedas (5+1)
    // Troco para 11: 2 moedas (10+1)
    // Troco para 15: 2 moedas (10+5)
    // Troco para 30: 2 moedas (25+5)
    // Troco para 99: 8 moedas (25+25+25+10+10+1+1+1+1)
}

Variante 2: Contagem de Formas

/// Conta o número de formas distintas de dar troco.
/// IMPORTANTE: iterar moedas no laço externo evita contar permutações.
fn contar_formas(moedas: &[u32], alvo: usize) -> u64 {
    let mut dp = vec![0u64; alvo + 1];
    dp[0] = 1; // Uma forma de dar troco para 0: não usar moedas

    // Para cada moeda, atualiza todos os valores que ela pode alcançar
    for &moeda in moedas {
        let c = moeda as usize;
        for v in c..=alvo {
            dp[v] += dp[v - c];
        }
    }

    dp[alvo]
}

fn main() {
    let moedas = vec![1, 2, 5];
    let alvo = 5;

    let formas = contar_formas(&moedas, alvo);
    println!("Formas de dar troco para {}: {}", alvo, formas); // 4

    // Moedas brasileiras: 5, 10, 25, 50 centavos; 1 real
    let reais = vec![5, 10, 25, 50, 100];
    let valor = 100; // 1 real em centavos
    let formas_real = contar_formas(&reais, valor);
    println!("Formas de trocar R$1,00: {}", formas_real);
}

Atenção ao ordenamento dos laços: Na contagem de formas, o laço externo itera sobre moedas e o interno sobre valores. Se invertermos, contaríamos permutações em vez de combinações (por exemplo, [1,2] e [2,1] seriam contados como formas distintas).

Otimização de Espaço

As soluções bottom-up já usam apenas O(V) de espaço — um único vetor unidimensional. Esta é a versão natural otimizada para o problema do troco, diferente de problemas como a mochila 0/1 que começam com tabela 2D.

Para a versão com memoização, o espaço também é O(V) pois o cache armazena no máximo V+1 entradas.

Reconstruindo a Solução

Para saber quais moedas foram usadas:

/// Reconstrói quais moedas foram usadas para o troco mínimo.
fn reconstruir_troco(moedas: &[u32], alvo: usize) -> Option<Vec<u32>> {
    let mut dp = vec![usize::MAX; alvo + 1];
    // moeda_usada[v] = qual moeda foi usada para chegar ao valor v
    let mut moeda_usada = vec![0u32; alvo + 1];
    dp[0] = 0;

    for v in 1..=alvo {
        for &moeda in moedas {
            let c = moeda as usize;
            if c <= v && dp[v - c] != usize::MAX && dp[v - c] + 1 < dp[v] {
                dp[v] = dp[v - c] + 1;
                moeda_usada[v] = moeda;
            }
        }
    }

    if dp[alvo] == usize::MAX {
        return None;
    }

    // Reconstrói a lista de moedas
    let mut resultado = Vec::new();
    let mut restante = alvo;
    while restante > 0 {
        let moeda = moeda_usada[restante];
        resultado.push(moeda);
        restante -= moeda as usize;
    }

    Some(resultado)
}

fn main() {
    let moedas = vec![1, 5, 10, 25];

    for alvo in [30, 41, 99] {
        match reconstruir_troco(&moedas, alvo) {
            Some(usadas) => {
                println!("Troco para {}: {} moedas -> {:?}", alvo, usadas.len(), usadas);
            }
            None => println!("Troco para {}: impossível", alvo),
        }
    }
    // Troco para 30: 2 moedas -> [25, 5]
    // Troco para 41: 4 moedas -> [25, 10, 5, 1]
    // Troco para 99: 8 moedas -> [25, 25, 25, 10, 10, 1, 1, 1, 1]
}

Comparação: Abordagem Gulosa versus DP

Para moedas canônicas (como as brasileiras ou americanas), a abordagem gulosa funciona: sempre escolha a maior moeda possível. Mas nem sempre!

/// Abordagem gulosa: funciona para moedas canônicas, falha para outras.
fn troco_guloso(moedas: &mut [u32], alvo: u32) -> Option<Vec<u32>> {
    moedas.sort_unstable_by(|a, b| b.cmp(a)); // Ordena decrescente
    let mut restante = alvo;
    let mut resultado = Vec::new();

    for &moeda in moedas.iter() {
        while moeda <= restante {
            resultado.push(moeda);
            restante -= moeda;
        }
    }

    if restante == 0 {
        Some(resultado)
    } else {
        None
    }
}

fn main() {
    // Caso onde guloso funciona
    let mut moedas1 = vec![1, 5, 10, 25];
    println!("Guloso para 30: {:?}", troco_guloso(&mut moedas1, 30));
    // Some([25, 5]) — correto!

    // Caso onde guloso FALHA
    let mut moedas2 = vec![1, 3, 4];
    println!("Guloso para 6: {:?}", troco_guloso(&mut moedas2, 6));
    // Some([4, 1, 1]) = 3 moedas — ERRADO!
    // DP encontra: [3, 3] = 2 moedas

    let moedas3 = vec![1, 3, 4];
    match reconstruir_troco(&moedas3, 6) {
        Some(r) => println!("DP para 6: {:?} = {} moedas", r, r.len()),
        None => println!("Impossível"),
    }
}

fn reconstruir_troco(moedas: &[u32], alvo: usize) -> Option<Vec<u32>> {
    let mut dp = vec![usize::MAX; alvo + 1];
    let mut moeda_usada = vec![0u32; alvo + 1];
    dp[0] = 0;
    for v in 1..=alvo {
        for &moeda in moedas {
            let c = moeda as usize;
            if c <= v && dp[v - c] != usize::MAX && dp[v - c] + 1 < dp[v] {
                dp[v] = dp[v - c] + 1;
                moeda_usada[v] = moeda;
            }
        }
    }
    if dp[alvo] == usize::MAX { return None; }
    let mut resultado = Vec::new();
    let mut restante = alvo;
    while restante > 0 {
        resultado.push(moeda_usada[restante]);
        restante -= moeda_usada[restante] as usize;
    }
    Some(resultado)
}

Exercícios Práticos

  1. Moedas com limite: Cada denominação tem um número máximo de cópias disponíveis. Por exemplo, você tem 3 moedas de 1, 2 moedas de 5 e 1 moeda de 10. Modifique a solução para respeitar esses limites (bounded knapsack).

  2. Troco com menor número de denominações: Em vez de minimizar o total de moedas, minimize o número de denominações distintas usadas.

  3. Verificar sistema canônico: Dado um conjunto de moedas, determine se a abordagem gulosa sempre dá a resposta ótima. Dica: teste todos os valores até moeda_max^2.

  4. Probabilidade de troco: Dado que a máquina de troco seleciona moedas uniformemente ao acaso (dentre as que cabem), qual a probabilidade de dar o troco mínimo? Simule com Monte Carlo.

Veja Também