Problema
Ogni persona deve effettuare esattamente una corsa. Qualsiasi gruppo può condividere una corsa se la somma dei loro pesi non supera la capacità. Le persone possono essere raggruppate liberamente; l'ordine di input non ha importanza. Minimizza il numero di corse.
Implementa elevator_rides(weights, capacity).
Input
weights: Il peso di ciascuna persona.
capacity: Il peso massimo totale consentito in una corsa.
Output
Restituisci il numero minimo di corse.
Vincoli
1 ≤ persone ≤ 20. 1 ≤ capacità ≤ 1.000.000.000. Ogni peso è compreso tra 1 e capacità.
Esempi
Input:
weights = [3, 4, 5]
capacity = 7
Output atteso:
expected = 2Input:
std::vector<long long> weights = {3, 4, 5};
long long capacity = 7;
Output atteso:
long long expected = 2;Input:
long[] weights = new long[] {3, 4, 5};
long capacity = 7;
Output atteso:
long expected = 2;Spiegazione
Manda insieme 3 + 4 e 5 da solo. Il peso totale 12 non può stare in una sola corsa con capacità 7.
Input:
weights = [2, 2, 2]
capacity = 6
Output atteso:
expected = 1Input:
std::vector<long long> weights = {2, 2, 2};
long long capacity = 6;
Output atteso:
long long expected = 1;Input:
long[] weights = new long[] {2, 2, 2};
long capacity = 6;
Output atteso:
long expected = 1;Spiegazione
Tutte e tre le persone stanno insieme perché 2 + 2 + 2 = 6.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Dato che il numero di persone è piccolo, considera i sottoinsiemi invece delle singole corse.
Suggerimento 2
Per ogni sottoinsieme, traccia sia quante corse servono sia quanto è piena l'ultima corsa corrente.
Suggerimento 3
Quando due stati usano lo stesso numero di corse, preferisci quello con carico corrente minore.
Complessità attesa
tempo O(2^n * n), spazio aggiuntivo O(2^n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.