Софтуерно Инженерство
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
MartinBG avatar MartinBG 780 Точки
Best Answer

Да, решението от упражнението не е точно, въпреки, че минава успещно в Judge.

Ето моето решение на задачата - простичко, но би трябвало да работи коректно и при по-засукани входни данни.

 

0
Zenith avatar Zenith 1 Точки

Работи безотказно! Интересен подход. Не би ми хрумнало подобно решение. Cheers!

0
Innos avatar Innos SoftUni Team 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