Schwierig 1 gelöst 100.0% Erfolgsquote

Minimale Aufzüge

Teile Personen in möglichst wenige Aufzugsfahrten mit Gewichtsbeschränkung ein.

Das lernst du

  • Personengruppen als Bitmasken darstellen
  • Pro Teilmenge beste Fahrten und letztes Fahrtgewicht speichern
  • Exponentielle Suchräume geschickt behandeln

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

Beispiel 1
Eingabe:
weights = [3, 4, 5]
capacity = 7

Erwartete Ausgabe:
expected = 2
Eingabe:
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.

Beispiel 2
Eingabe:
weights = [2, 2, 2]
capacity = 6

Erwartete Ausgabe:
expected = 1
Eingabe:
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 831 ms - 4/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.