Problem
Jede Person muss genau einmal fahren. Jede Gruppe kann gemeinsam fahren, wenn die Summe ihrer Gewichte die Kapazität nicht überschreitet. Die Gruppierung der Personen ist beliebig; die Reihenfolge der Eingabe spielt keine Rolle. Minimiere die Anzahl der Fahrten.
Implementiere elevator_rides(weights, capacity).
Eingabe
weights: Das Gewicht jeder Person.
capacity: Das maximal erlaubte Gesamtgewicht pro Fahrt.
Ausgabe
Gib die minimale Anzahl an Fahrten zurück.
Einschränkungen
1 ≤ Personen ≤ 20. 1 ≤ Kapazität ≤ 1.000.000.000. Jedes Gewicht liegt zwischen 1 und Kapazität.
Beispiele
Eingabe:
weights = [3, 4, 5]
capacity = 7
Erwartete Ausgabe:
expected = 2Eingabe:
std::vector<long long> weights = {3, 4, 5};
long long capacity = 7;
Erwartete Ausgabe:
long long expected = 2;Eingabe:
long[] weights = new long[] {3, 4, 5};
long capacity = 7;
Erwartete Ausgabe:
long expected = 2;Erläuterung
Schicke 3 + 4 zusammen und 5 einzeln. Das Gesamtgewicht 12 passt nicht in eine Fahrt mit Kapazität 7.
Eingabe:
weights = [2, 2, 2]
capacity = 6
Erwartete Ausgabe:
expected = 1Eingabe:
std::vector<long long> weights = {2, 2, 2};
long long capacity = 6;
Erwartete Ausgabe:
long long expected = 1;Eingabe:
long[] weights = new long[] {2, 2, 2};
long capacity = 6;
Erwartete Ausgabe:
long expected = 1;Erläuterung
Alle drei Personen passen zusammen, da 2 + 2 + 2 = 6.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Da die Personenzahl klein ist, betrachte Teilmengen statt einzelner Fahrten.
Hinweis 2
Verfolge für jede Teilmenge sowohl die Anzahl der Fahrten als auch, wie voll die aktuelle letzte Fahrt ist.
Hinweis 3
Wenn zwei Zustände gleich viele Fahrten verwenden, bevorzuge den mit der kleineren aktuellen Last.
Erwartete Komplexität
Zeit O(2^n * n), zusätzlicher Speicher O(2^n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.