Задача: Оптимальное распределение задач

Описание задачи

Предположим, у нас есть n задач, каждая из которых имеет определенную стоимость выполнения c_i и время выполнения t_i. Нам нужно распределить эти задачи между k сотрудниками таким образом, чтобы минимизировать максимальное время, затрачиваемое на выполнение задач одним сотрудником.

Пример входных данных

• Количество задач: n = 5
• Количество сотрудников: k = 2
• Стоимость и время выполнения задач:
  • Задача 1: c_1 = 10, t_1 = 3
  • Задача 2: c_2 = 20, t_2 = 2
  • Задача 3: c_3 = 30, t_3 = 4
  • Задача 4: c_4 = 40, t_4 = 1
  • Задача 5: c_5 = 50, t_5 = 5

Почему используется динамическое программирование?

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

Решение с использованием динамического программирования

1. Определение состояния:

   • dp[i][j] — минимальное время, за которое можно распределить первые i задач между j сотрудниками.

2. Базовый случай:

   • dp[0][0] = 0 — если задач нет, то время равно 0.
   • dp[i][0] = ∞ — если сотрудников нет, то распределить задачи невозможно.

3. Рекуррентное соотношение:

   • Для каждой задачи i и каждого сотрудника j мы пытаемся распределить задачи так, чтобы минимизировать максимальное время:

     dp[i][j] = min(dp[i][j], max(dp[i-1][j-1], t_i))
     

4. Заполнение таблицы:

   • Проходим по всем задачам и сотрудникам, заполняя таблицу dp.

5. Результат:

   • Искомое значение будет находиться в dp[n][k].

Пример кода на Python

def optimal_task_distribution(n, k, tasks):
    dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for i in range(1, n + 1):
        for j in range(1, k + 1):
            max_time = 0
            for m in range(i):
                max_time = max(max_time, tasks[m][1])
                dp[i][j] = min(dp[i][j], max(dp[m][j-1], max_time))

    return dp[n][k]

# Пример использования
tasks = [(10, 3), (20, 2), (30, 4), (40, 1), (50, 5)]
n = 5
k = 2
print(optimal_task_distribution(n, k, tasks))