A Chciwy algorytm dla k-ograniczonych zasobów

Question

Studiuję chciwe algorytmy i zastanawiam się, jakie jest rozwiązanie dla innego przypadku.

W przypadku problemu z wyborem przedziału, chcemy wybrać maksymalną liczbę działań, które nie kolidują ze sobą, dlatego wybór pracy z najwcześniejszym czasem wykańczania działa.

Inny przykład; mamy podaną pracę i chcemy kupić jak najmniejszą ilość zasobów. Tutaj możemy posortować wszystkie zadania od lewej do prawej, a gdy napotkamy nowy punkt początkowy, zwiększamy licznik i gdy napotykamy punkt końcowy, zmniejszamy licznik. Tak więc największą wartością, jaką otrzymamy z tego licznika, będzie liczba zasobów, które musimy kupić.

Ale na przykład, co jeśli mamy n zadań, ale k zasobów? Co jeśli nie możemy sobie pozwolić na więcej niż k zasobu? Jak powinno być chciwe rozwiązanie, aby usunąć jak najwięcej zadań, aby to spełnić?

Również, jeśli istnieje konkretna nazwa dla ostatniego problemu, który napisałem, byłbym szczęśliwy, słysząc to.

Answer 1

To wygląda na ogólny przypadek wersji, w której mamy tylko jeden zasób.

Intuicyjnie, nadal warto posortować zadania według czasu zakończenia i wziąć je kolejno jeden po drugim w tej kolejności. Teraz, zamiast zakończenia ostatniego zlecenia, śledzimy końcowe czasy ostatnich zadań zaakceptowanych w naszych zasobach. Dla każdego zadania sprawdzamy, czy bieżący czas rozpoczęcia pracy jest większy niż ostatnie zadanie w którymkolwiek z naszych zasobów. Jeśli taki zasób nie zostanie znaleziony, pomijamy tę pracę i ruszamy dalej. Jeśli zostanie znaleziony jeden zasób, przypisujemy to zadanie do tego zasobu i aktualizujemy czas zakończenia. Jeśli istnieje więcej niż jeden zasób zdolny do podjęcia tego zadania, ma sens przypisanie go do zasobu z najnowszym czasem zakończenia.

Nie mam naprawdę dowodu na tę chciwą strategię, więc może się mylić. Ale nie mogę wymyślić przypadku, w którym zmiana wyboru może umożliwić nam dopasowanie większej liczby miejsc pracy.