Ein Greedy-Algorithmus für k-begrenzte Ressourcen

Question

Ich studiere gierige Algorithmen und frage mich nach der Lösung für einen anderen Fall.

Für das Problem der Intervallauswahl wollen wir die maximale Anzahl von Aktivitäten auswählen, die nicht miteinander kollidieren, so dass die Auswahl des Jobs mit der frühesten Endzeit funktioniert.

Ein anderes Beispiel: Wir haben n Aufträge gegeben und wollen so wenig Ressourcen wie möglich kaufen. Hier können wir alle Aufträge von links nach rechts sortieren, und wenn wir auf einen neuen Startpunkt treffen, erhöhen wir einen Zähler, und wenn wir auf einen Endpunkt treffen, verringern wir den Zähler. Der größte Wert, den wir von diesem Zähler erhalten, ist also die Anzahl der Ressourcen, die wir kaufen müssen.

Aber was ist zum Beispiel, wenn wir n Aufgaben, aber k Ressourcen haben? Was ist, wenn wir uns nicht mehr als k Ressourcen leisten können? Wie sollte eine gierige Lösung aussehen, um so wenige Aufgaben wie möglich zu entfernen, um dem gerecht zu werden?

Auch wenn es einen spezifischen Namen für das letzte Problem gibt, das ich geschrieben habe, würde ich mich freuen, diesen zu hören.

Answer 1

Dies sieht wie ein allgemeiner Fall der Version aus, bei der wir nur eine Ressource haben.

Intuitiv ist es sinnvoll, die Aufträge weiterhin nach Endzeit zu sortieren und sie in dieser Reihenfolge nacheinander abzuarbeiten. Anstelle der Endzeit des letzten Auftrags erfassen wir nun die Endzeiten der letzten k Aufträge, die in unsere Ressourcen aufgenommen wurden. Für jeden Auftrag prüfen wir, ob die Startzeit des aktuellen Auftrags größer ist als die des letzten Auftrags in einer unserer Ressourcen. Wird keine solche Ressource gefunden, wird der Auftrag übersprungen und weitergemacht. Wenn eine Ressource gefunden wird, wird der Auftrag dieser Ressource zugewiesen und die Endzeit aktualisiert. Wenn es mehr als eine Ressource gibt, die diesen Auftrag übernehmen kann, ist es sinnvoll, ihn der Ressource mit der spätesten Endzeit zuzuweisen.

Ich habe nicht wirklich einen Beweis für diese gierige Strategie, daher kann sie durchaus falsch sein. Aber ich kann mir keinen Fall vorstellen, in dem eine Änderung der Wahl es uns ermöglichen würde, mehr Arbeitsplätze zu schaffen.