Оптимальный алгоритм

Question

У двух рабочих есть несколько задач. Предположим, что у задач есть продолжительность 14, 7, 2, 4. Следующая задача уходит к первому свободному работнику.Двое рабочих должны выполнить несколько заданий за один день.Одна и та же задача занимает одинаковое время у двух рабочих.Наша цель - завершить задачи как можно скорее.

Два вопроса: 1. показать, что алгоритм всегда выполняет задачу до времени 2 * T, T - оптимальное время завершения.2. Выразите оптимальное планирование с помощью воскресения (многомерного)

Не HW PRoblem

Пожалуйста, дайте мне несколько советов

Что такое многомерная рекурсия?

Answer 1

Так как вы спрашиваете предложения ...

Попробуйте нарисовать проблему. Укажите график времени для работника № 1 и работника № 2 и укажите, над какими задачами они работают в течение какого промежутка времени. Как только вы поймете, почему этот алгоритм завершается менее чем за 2 * T времени, вы можете начать выяснять, как формально доказать это.