To mój pierwszy eksperyment z asymptotycznym wyzwaniem złożoności, chociaż cieszę się z odpowiedzi w całości w kodzie, pod warunkiem, że zawierają wyjaśnienie złożoności czasu.
Mam następujący problem.
Rozważ zadania T_1, ... T_n i proc. M_1, ..., M_m. Każde zadanie zajmuje określoną ilość czasu w zależności od procedur.
Każde zadanie kosztuje również pewną kwotę do wykonania w zależności od proc.
Zadania muszą być wykonywane w ścisłej kolejności (nie można ich wykonywać równolegle), a zmiana proc zajmuje dużo czasu. Zadania nie można przenosić z jednego procesu do drugiego po jego uruchomieniu.
Wreszcie każde zadanie musi zostać zakończone do określonego czasu.
zadanie
Celem jest podanie algorytmu (lub jakiegoś kodu), który przy pięciu tabelach powyższego formularza, minimalizuje całkowity koszt wykonania wszystkich zadań, jednocześnie upewniając się, że wszystkie zadania zostały wykonane w wyznaczonym terminie. Jeśli nie jest to możliwe, po prostu informujemy, że nie można tego zrobić.
wynik
Powinieneś dać dużą Oh złożoność swojego rozwiązania w kategoriach zmiennych n, mi id, gdzie d jest ostatnim terminem. W twojej wielkiej złożoności Oh nie powinno być żadnych niepotrzebnych stałych. Tak więc na przykład O (n / 1000) należy zapisać jako O (n).
Twój wynik obliczany jest po prostu przez ustawienie n = 100, m = 100 id = 1000 w podanej złożoności. Chcesz mieć jak najmniejszy wynik.
remis
W przypadku remisu pierwsza odpowiedź wygrywa.
dodane notatki
log
w czasie złożoność odpowiedzi zostanie wzięta za podstawę 2.
tablica wyników
- 10 ^ 202 z KSFT ( Python ) Najpierw przesłane, więc dostaje nagrodę.
- 10 ^ 202 od Dominika Müllera ( Scala )
O(m ^ n)
. Żaden algorytm nie będzie „szybszy” niż to. Przycinanie oparte na maksymalnym wymaganym czasie lub koszcie nie zmienia złożoności algorytmu, ani nie ma zarówno kosztu w dolarach, jak i kosztu czasu, dlategod
nie jest elementem złożoności.Odpowiedzi:
Wynik: 10 ^ 202
Chciałbym mieć teraz wsparcie LaTeX ...
Ponieważ nikt inny nie odpowiedział, pomyślałem, że spróbuję, chociaż nie jest to zbyt wydajne. Nie jestem jednak pewien, co to za wielkie O.
Myślę, że to działa. Przynajmniej tak jest w przypadku jedynego opublikowanego przypadku testowego.
Przyjmuje dane wejściowe jak w pytaniu, z wyjątkiem etykiet maszyn i numerów zadań oraz średników zamiast podziałów linii.
źródło
Zaznacz wszystko - Scala
Szacowany wynik: 2 mln ^ n
Zaczynam od każdej maszyny i powtarzam wszystkie zadania, aby utworzyć wszystkie permutacje poprzez zadania z różnymi maszynami, które dotrzymują terminów. Oznacza to, że jeśli wszystko jest na czas, uzyskałbym 9 możliwych ścieżek z 2 maszynami i 3 zadaniami. (m ^ n) Następnie wybieram ścieżkę o najniższym koszcie.
Dane wejściowe mają następującą strukturę (-> wyjaśnia części i dlatego nie należy ich wprowadzać):
A oto kod:
Miałem też pomysł, aby zacząć od tyłu. Ponieważ zawsze możesz wybrać maszynę o najniższych kosztach, jeśli czas jest krótszy, niż różnica między poprzednim terminem a nowym. Nie zmniejszyłoby to jednak maksymalnego czasu działania, jeśli zadanie o lepszych kosztach trwa dłużej niż ostatni termin.
Aktualizacja
======
Oto kolejna konfiguracja. czas:
koszt:
czas przełączania:
koszt zmiany:
terminy:
Jako dane wejściowe do mojego programu:
Ten ma dwa rozwiązania: czas: 18, koszt: 15, ścieżka: Lista (M_1, M_1, M_1, M_2) czas: 18, koszt: 15, ścieżka: Lista (M_2, M_1, M_1, M_1)
Co nasuwa pytanie, jak należy sobie z tym poradzić. Czy wszystkie powinny być wydrukowane, czy tylko jeden? A jeśli czas byłby inny? Czy taki, który ma najniższy koszt i nie ma przekroczonego terminu, czy też powinien to być ten o najniższym czasie?
źródło
O(m^n)
czasu. Iteracja po każdej maszynie dla wszystkich zadań wymagaO(n*m^n)
czasu.O(n*m^n)
iteruje się po każdym zadaniu dla każdej ścieżki? I iteracja po każdej maszynie dla każdego zadania jakoś takO(n*m)
.O(n*m^n)
”.O(m*m^n)=O(m^n+1)
. Nadal jednak ten sam wynik.