Loading...
Zenith avatar Zenith 1 Точки

Алгоритми Юли 2017 Processor Scheduling

След доста мислене над тази задача се отказах и реших да погледна видеото от упражнението. Оказа се че колегата Грамов също се затрудни с нея. Разбираемо имайки предвид странно и неясно написаното условие. На 02:16:10 във видеото се вижда условие което judge системата възнаграждава със 100 точки. Това е решението преписано дословно. Реших да го препиша и дебъгна за да видя как работи и какво точно съм пропуснал. Идеята е да вземе най-големия срок и да го използва като лимит за броя на задачите които могат да се изпълнят преди него. Оказа се, обаче, че и то не следва условието на задачата - докато се опитвах да я напиша си създадох няколко теста, освен дадените, с цел да следя поведението на алгоритъма в различни ситуации. Пример: 

 

Tasks: 6
5 - 1
6 - 1
2 - 1
3 - 1
8 - 4
4 - 1

 

максималния брой задачи, които могат да се изпълнят е 2 - една която има deadline 1 и тази с deadline 4, тъй като по условие всяка задача се изпълнява за една единица време. Тоест изпълнявайки една от задачите всички (други) с deadline 1 не би трябвало да могат да се изпълнят тъй като срока им е минал. Въпреки това алгоритъма взима най-големия deadline - в случая 4 - и добавя задачи в списък докато броят на добавените елементи не стигне до maxDeadline (foreach loop-а на ред  27 от решението).
EDIT: Забравих да постна условието.
Някой може ли да удари едно рамо с решение което всъщност отговаря на условието?

0
Структури от данни и алгоритми 19/07/2017 23:46:08
Innos avatar Innos 419 Точки

Реалната хитрост на тази задача е да ги почнеш отзад напред. Ето няколко стъпките за оптимално решение:

  1. Намери най големият deadline - x
  2. Вземи всички task-ове с най големия deadline - x
  3. Сложи всички task-ове с deadline - x в някаква колекция (най-добре MaxHeap)
  4. Сложи за изпълнение на ход - x, task-a със най голяма стойност от колекцията
  5. Повтaряй стъпки 3-4 за deadline-ове (x - 1), (x - 2) и така нататък до началото.

 

Хитроста тук е че ако имаме някакъв максимален deadline - x, то единствените таскове който могат да се изпълнят на x-тият ход, са тези с deadline - x, измежду тях много лесно можем да решим кой е най добрият - този който има най голямо value. По същата логика на ход (x - 1), task-овете от които можем да избираме са всичките task-ове с deadline (x - 1) както и всички останали task-ове с deadline - x (всички освен тази която сме избрали за ход - x). Следвайки този ред можем да изберем оптималният task за всеки ход.

0
31/07/2017 23:51:29
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.