Alice, studentka, ma dużo pracy domowej w ciągu najbliższych tygodni. Każda praca domowa zabiera ją dokładnie jednego dnia. Każda pozycja ma również termin i negatywny wpływ na jej oceny (zakładamy liczbę rzeczywistą, punkty bonusowe za przyjęcie założenia porównywalności), jeśli nie dotrzyma terminu.
Napisz funkcję, która podając listę (termin, wpływ na ocenę) obliczy harmonogram zadań domowych do wykonania w dniu, który minimalizuje sumę złego wpływu na jej oceny.
Wszystkie prace domowe muszą zostać ostatecznie wykonane, ale jeśli nie dotrzyma terminu, nie ma znaczenia, jak późno ją oddaje.
W alternatywnym sformułowaniu:
ACME corp chce dostarczać wodę do klientów. Wszyscy mieszkają wzdłuż jednej pod górę ulicy. ACME ma kilka studni rozmieszczonych wzdłuż ulicy. Każda studnia zawiera wystarczającą ilość wody dla jednego klienta. Klienci licytują różne kwoty pieniędzy do dostarczenia. Woda płynie tylko w dół. Maksymalizuj przychody, wybierając klientów do dostarczenia.
Możemy posortować terminy za pomocą sortowania kubełkowego (lub po prostu założyć, że już posortowaliśmy według terminu).
Możemy łatwo rozwiązać problem za pomocą chciwego algorytmu, jeśli najpierw posortujemy według malejącego wpływu na ocenę. To rozwiązanie nie będzie lepsze niż O (n log n).
Zainspirowany przez medianę median i algorytmy losowego liniowego drzewa rozpinającego , podejrzewam, że możemy rozwiązać mój prosty problem planowania / przepływu również w (losowym?) Czasie liniowym.
Szukam:
- (potencjalnie losowy) liniowy algorytm czasu
- lub alternatywnie argument, że czas liniowy nie jest możliwy
Jako odskocznia:
- Udowodniłem już, że sama wiedza o tym, które przedmioty można wykonać przed upływem terminu, wystarczy do odtworzenia pełnego harmonogramu w czasie liniowym. (Ta wiedza leży u podstaw drugiego sformułowania, w którym pytam tylko o certyfikat).
- Prosty (integralny!) Program liniowy może modelować ten problem.
- Korzystając z dualności tego programu, można sprawdzić proponowane rozwiązanie w czasie liniowym pod kątem optymalności, jeśli podano również rozwiązanie dla podwójnego programu. (Oba rozwiązania można przedstawić w postaci liniowej liczby bitów.)
Idealnie chciałbym rozwiązać ten problem w modelu, który wykorzystuje tylko porównanie wpływów ocen i nie zakłada tam liczb.
Mam dwa podejścia do tego problemu - jeden oparty na pułapkach z wykorzystaniem terminu i wpływu, drugi podobny do QuickSelect polegający na wybieraniu losowych elementów przestawnych i dzieleniu elementów przez uderzenie. Oba mają najgorsze przypadki, które wymuszają O (n log n) lub gorszą wydajność, ale nie byłem w stanie zbudować prostego specjalnego przypadku, który obniżyłby wydajność obu.