Нахождение максимальной суммы счастья
У меня есть проблема, чтобы решить, и не вижу оптимального решения:/ Проблема заключается в:
У меня есть n рабочих и k рабочих мест. Каждая работа должна выполняться указанным количеством работников, и у каждого работника есть свой уровень счастья для каждой работы. Я должен составить график работы, чтобы работники были настолько счастливы, насколько это возможно. Итак, у меня есть массив a1 из int[n,k] (k >= n). k-й столбец i-й строки содержит предпочтения (число от 0 до 10) i-го работника для k-го задания. У меня также есть массив a2 из int[k], где i-й элемент содержит количество людей, которые будут выполнять эту работу. Каждый работник должен выполнять одинаковое количество работ. Я должен найти максимально возможную сумму счастья, зная, что n >= max(a2). Мое решение состоит в том, чтобы использовать рекурсию. Выберите первого работника для первой комбинации заданий, добавьте предпочтения к сумме, проверьте, больше ли сумма, чем уже найденное максимальное значение, и, если это так, перейдите к следующему работнику. Вернувшись, проверьте следующую комбинацию для первого работника и т. Д. Это хорошо работает для небольшого количества работников, но требует большой вычислительной сложности для решения больших проблем. У вас есть идея для лучшего решения?
PS. Парень с другого сайта рекомендовал мне использовать венгерский алгоритм, но он предполагает, что n == k, и я не знаю, как заставить его работать с n <= k
PS2 пример:
a1:
job1 job2 job3 job4
wokrer1 1 3 4 2
worker2 9 8 1 2
worker3 6 7 8 9
a2:
job1 job2 job3 job4
count 1 2 2 1
example solution:
worker1: job2, job3 (7)
worker2: job1, job2 (17)
worker3: job3, job4 (17)
sum: 41
2 ответа
Это похоже на транспортную проблему для меня. Это может быть решено с помощью венгерского алгоритма, хотя. Сначала давайте настроим матрицу для венгерского алгоритма.
Венгерский алгоритм используется, чтобы найти минимальную сумму. Чтобы решить эту проблему с максимальной суммой, вы должны сначала инвертировать все ваши ценности счастья.
J1 J2 J3 J4
W1 1 3 4 2
W2 9 8 1 2
W3 6 7 8 9
Вычтите каждое значение на наибольшее значение в матрице.
Наибольшее значение в этой матрице составляет 9.
J1 J2 J3 J4
W1 9-1 9-3 9-4 9-2
W2 9-9 9-8 9-1 9-2
W3 9-6 9-7 9-8 9-9
J1 J2 J3 J4
W1 8 6 5 7
W2 0 1 8 7
W3 3 2 1 0
Теперь, как вы заметили, венгерский алгоритм работает только с квадратными матрицами. Чтобы заставить его работать на прямоугольной матрице, мы должны сделать его квадратным. Мы можем сделать это, добавив фиктивные строки или столбцы, заполненные нулями.
J1 J2 J3 J4
W1 8 6 5 7
W2 0 1 8 7
W3 3 2 1 0
WD 0 0 0 0
Теперь, когда у нас есть это в удобной форме, мы можем решить за минимальную сумму. Я собираюсь перейти к решению, так как инструкции по использованию венгерского алгоритма легко доступны в другом месте.
W1 -> J3
W2 -> J1
W3 -> J4
WD -> J2 (Except this is a dummy row so it doesn't count.)
Теперь мы назначили одну работу каждому из наших работников. Это где ваш второй массив вступает в игру.
J1 J2 J3 J4
1 2 2 1
Мы назначили работника на рабочие места 1, 3 и 4, поэтому мы вычтем 1 из их соответствующих значений.
J1 J2 J3 J4
0 2 1 0
Поскольку нам больше не нужен кто-либо для выполнения заданий 1 или 4, мы также можем удалить их столбцы из нашей матрицы счастья.
J2 J3
W1 6 5
W2 1 8
W3 2 1
У нас все еще есть работа, поэтому мы снова проходим через этот процесс.
Добавьте фиктивные столбцы, чтобы сделать матрицу квадратной.
J2 J3 JD
W1 6 5 0
W2 1 8 0
W3 2 1 0
и решить. Помните, что столбцы предназначены для заданий 2 и 3, а не 1 и 2.
W1 -> JD
W2 -> J2
W3 -> J3
Теперь мы дважды прошли алгоритм и назначили пять заданий.
W1 -> J3
W2 -> J1, J2
W3 -> J4, J3
Теперь мы снова пройдем весь процесс. Поскольку существует только одно задание, которое нужно назначить, и один человек, которому нужно назначить его (W1 назначена только одна работа, но им всем должен быть назначен один и тот же номер.), Мы можем просто перейти к нашему окончательному решению.
W1 -> J3, J2
W2 -> J1, J2
W3 -> J4, J3
и ценности счастья для этого:
W1 -> 4 + 3 = 7
W2 -> 9 + 8 = 17
W3 -> 9 + 8 = 17
в общей сложности 41.
Способ использования венгерского алгоритма состоит в том, чтобы сделать a2[i] вершины для работы i, Надеюсь, что a2 суммы массива в n, Если k << nтогда вам, вероятно, лучше сформулировать проблему минимальной циркуляции.