#algorithm
#алгоритм
Вопрос:
У двух работников есть несколько задач.Предположим, что задачи имеют длительность 14, 7, 2, 4. Следующая задача переходит к первому свободному рабочему. Два работника должны выполнить несколько задач за один день. Одна и та же задача занимает одинаковое время у двух рабочих. Наша цель — завершить задачи как можно скорее.
Два вопроса: 1. покажите, что алгоритм всегда завершает задачу до времени 2 * T, T — оптимальное время завершения. 2. выразите оптимальное планирование с помощью повторного использования (многомерного)
Проблема не в HW
Пожалуйста, дайте мне несколько предложений
Что такое многомерная рекурсия?
Комментарии:
1. Вопрос слишком сложен для понимания. «T — оптимальное время завершения»: оптимально в каком случае? А многомерная рекурсия? Если это не домашняя проблема, то что вы на самом деле пытаетесь решить?
2. @Justin: Я предполагаю, что это оптимальное из всех возможных решений.
3. Достижение времени 2 * T является тривиальным. Пусть все делает один рабочий, поскольку оптимальное время не может быть меньше половины общего времени для всех задач.
4. Пояснение к предыдущему комментарию: при любом порядке выполнения задач время выполнения будет меньше 2 * T, поскольку оптимальное время T составляет не менее 1/2 от общего количества всех задач.
5. Просто любопытно, если это «Не проблема HW», то откуда она взялась? Люди не формулируют свои собственные вопросы таким образом.
Ответ №1:
Поскольку вы просите предложений…
Попробуйте нарисовать проблему в деталях. Составьте временную шкалу для работника № 1 и работника № 2 и укажите, над какими задачами они работают в течение каких промежутков времени. Как только вы поймете, почему этот алгоритм завершается менее чем за 2 * T времени, вы сможете начать выяснять, как формально доказать это.