Заменитель Планирование программы/Алгоритм

Question

Я работаю над следующей проблемой сейчас для клиента, который позволит создать наиболее экономичный график (использует наименее заменители) при условии, что:

• Замена должен работать на месте учителей для как последовательное время как можно (* Не огромная проблема)
• Subs может работать только в течение 6 периодов

до сих пор у меня есть класс Учителя (как показано ниже) и класс Organizer, который фактически создает оптимальный график. Прямо сейчас у меня есть только программный цикл через сетку, заполняющий каждую замену.

Teacher[] t= new Teacher[14]; 
Organizer o = new Organizer(t);   
o.sort(); 

int[][] g = o.getGrid(); 

Пример ввода:

t[0] = new Teacher("Teacher 1", "Mr", new int[]{1,0,1,0,0,0,0}); 
t[1] = new Teacher("Teacher 2","Mr", new int[]{1,1,0,1,1,0,1}); 
t[2] = new Teacher("Teacher 3","Mr", new int[]{0,1,1,1,1,1,0}); 
t[3] = new Teacher("Teacher 4","Mr", new int[]{1,1,0,1,1,0,1}); 
t[4] = new Teacher("Teacher 5","Mr", new int[]{1,1,0,0,1,1,1}); 
t[5] = new Teacher("Teacher 6", "Mr", new int[]{1,1,1,0,0,1,1}); 
t[6] = new Teacher("Teacher 7", "Mr", new int[]{0,0,1,0,1,1,1}); 
t[7] = new Teacher("Teacher 8", "Mr", new int[]{1,1,0,0,1,1,1}); 
t[8] = new Teacher("Teacher 9", "Mr", new int[]{1,1,1,1,1,0,0}); 
t[9] = new Teacher("Teacher 10", "Mr", new int[]{0,0,0,1,1,1,0}); 
t[10] = new Teacher("Teacher 11", "Mr", new int[]{0,0,1,0,0,1,1}); 
t[11] = new Teacher("Teacher 12", "Mr", new int[]{0,0,1,1,0,1,0}); 
t[12] = new Teacher("Teacher 13", "Mr", new int[]{1,1,1,1,0,0,0}); 
t[13] = new Teacher("Teacher 14", "Mr", new int[]{1,1,0,1,1,0,1}); 

Выход для выше (с помощью алгоритма я использую):

    P1 P2 P3 P4 P5 P6 P7 
Teacher 1   1 - 1 - - - - 
Teacher 2   2 1 - 1 1 - 1 
Teacher 3   - 2 2 2 2 2 - 
Teacher 4   3 3 - 3 3 - 3 
Teacher 5   4 4 - - 4 3 4 
Teacher 6   5 5 4 - - 4 5 
Teacher 7   - - 5 - 5 5 6 
Teacher 8   6 6 - - 6 6 7 
Teacher 9   7 7 6 7 7 - - 
Teacher 10   - - - 8 8 7 - 
Teacher 11   - - 8 - - 8 8 
Teacher 12   - - 9 9 - 9 - 
Teacher 13   8 9 10 10 - - - 
Teacher 14   9 10 - 11 9 - 10 

Как вы можете видеть, программа просто петли по допустимых пространств , заполняя их субтитрами до тех пор, пока суб достигает своих максимальных периодов обучения, а затем начинает новый юнит. Дело в том, что я смог получить количество подложек, используемых до 10, когда делаю это вручную, поэтому я пытался найти более эффективный алгоритм, безрезультатно.

Для этого ввода минимальное количество используемых подсетей - 9 (ограничено столбцом P2), поэтому я хотел бы увидеть, есть ли какой-либо возможный способ, которым я могу выполнить это число, или, соответственно, 10 подсетей. Заранее спасибо!

Answer 1

Для каждой колонки укажите количество открытых пространств.

Поместите каждый суб-первый в столбцы с самыми открытыми пространствами, а затем произвольно. Этот алгоритм решит вашу проблему с 10 subs.

В вашем конкретном примере имеется 59 пробелов. Учитывая, что каждый юг может заполнять только 6 пробелов, 10 - это наименьшее количество подсистем, которые могут работать. Я считаю, что он всегда найдет оптимальное решение.

(Я проигнорировал правило ваших последовательных дней. Правило «затем случайно» можно заменить чем-то, что пытается его оптимизировать ...)