Problema
Cada pessoa deve fazer exatamente uma viagem. Qualquer grupo pode compartilhar uma viagem se a soma de seus pesos não exceder a capacidade. As pessoas podem ser reagrupadas livremente; a ordem de entrada não importa. Minimize o número de viagens.
Implemente elevator_rides(weights, capacity).
Entrada
weights: O peso de cada pessoa.
capacity: O peso máximo combinado em uma viagem.
Saída
Retorne o número mínimo de viagens.
Restrições
1 ≤ pessoas ≤ 20. 1 ≤ capacidade ≤ 1.000.000.000. Cada peso está entre 1 e capacidade.
Exemplos
Entrada:
weights = [3, 4, 5]
capacity = 7
Saída esperada:
expected = 2Entrada:
std::vector<long long> weights = {3, 4, 5};
long long capacity = 7;
Saída esperada:
long long expected = 2;Entrada:
long[] weights = new long[] {3, 4, 5};
long capacity = 7;
Saída esperada:
long expected = 2;Explicação
Envie 3 + 4 juntos e 5 separado. O peso total 12 não cabe em uma viagem com capacidade 7.
Entrada:
weights = [2, 2, 2]
capacity = 6
Saída esperada:
expected = 1Entrada:
std::vector<long long> weights = {2, 2, 2};
long long capacity = 6;
Saída esperada:
long long expected = 1;Entrada:
long[] weights = new long[] {2, 2, 2};
long capacity = 6;
Saída esperada:
long expected = 1;Explicação
Todas as três pessoas cabem juntas porque 2 + 2 + 2 = 6.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Como o número de pessoas é pequeno, considere subconjuntos em vez de viagens individuais.
Dica 2
Acompanhe, para cada subconjunto, quantas viagens são usadas e o quão cheia está a última viagem.
Dica 3
Quando dois estados usam o mesmo número de viagens, prefira o que tiver menor carga atual.
Complexidade esperada
tempo O(2^n * n), espaço extra O(2^n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.