Редактирование: QpmtnSumCi

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 10: Строка 10:
  
 
=== Псевдокод ===
 
=== Псевдокод ===
Алгоритм принимает на вход два массива {{---}} массив с объемами работ и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй {{---}} номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке.
+
Алгоритм принимает на вход два массива {{---}} массив с количеством обработки нужным для каждой работы и массив скоростей обработки станков, и возвращает массив длинной <tex>m</tex>, в котором на <tex>i</tex>-ой позиции содержится расписание для <tex>i</tex>-ого станка, представляющей собой вектор троек, где первый элемент является номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке.
  '''function''' scheduling(p: '''int'''[n], v: '''int'''[n]) -> '''vector<int, int, int, int>'''
+
  '''function''' scheduling(p: '''Array'''[int], v: '''Array'''[int]) -> '''Array[Vector[(int, int, int)]]'''
 
     '''int''' time = 0 <font color=green>// текущее время на всех станках</font>
 
     '''int''' time = 0 <font color=green>// текущее время на всех станках</font>
     '''vector<int, int, int, int>''' ans <font color=green> // вектор, куда будет записан ответ</font>
+
     '''Array[Vector[(int, int, int)]]''' ans = new '''Array[Vector[(int, int, int)]]'''(m) <font color=green> // массив длинной m, куда будет записан ответ</font>
 
     sort(p) <font color=green>// сортируем времена обработки работ в невозрастающем порядке</font>
 
     sort(p) <font color=green>// сортируем времена обработки работ в невозрастающем порядке</font>
 
     sort(v) <font color=green>// сортируем скорости обработки станков в невозрастающем порядке</font>
 
     sort(v) <font color=green>// сортируем скорости обработки станков в невозрастающем порядке</font>
Строка 20: Строка 20:
 
         '''int''' dt = p[i] / v[1] <font color=green>// время обработки самой короткой доступной задачи на самом быстром станке</font>
 
         '''int''' dt = p[i] / v[1] <font color=green>// время обработки самой короткой доступной задачи на самом быстром станке</font>
 
         '''for''' j = i '''downto''' k = max(1, i - m + 1)
 
         '''for''' j = i '''downto''' k = max(1, i - m + 1)
             ans.push(1 + i - j, j, time, time + dt) <font color=green>// Назначаем на станок <tex>M_{1+i-j}</tex> работу j на время от time до time + dt</font>
+
             ans[1 + i - j].push(j, time, time + dt) <font color=green>// Назначаем работу j на станок <tex>M_{1+i-j}</tex> на время от time до time + dt</font>
 
             p[j] = p[j] - dt * v[1 + i - j] <font color=green>// уменьшаем количество обработки, оставшейся для j-ой работы</font>
 
             p[j] = p[j] - dt * v[1 + i - j] <font color=green>// уменьшаем количество обработки, оставшейся для j-ой работы</font>
 
         time = time + dt <font color=green>// обновляем текущее время</font>
 
         time = time + dt <font color=green>// обновляем текущее время</font>

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)