Жадный алгоритм для завершения задачи с ограничением времени

Question

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

Вопрос:

Вы работаете над проектом программирования. Есть n Java-классов C1, C2, ..., Cn (так говорит босс-архитектор). Архитектор также говорит, что эти классы должны быть реализованы по порядку (вам не разрешено выполнять C2 до завершения C1 и т. Д.).

Каждый из классов Java занимает не более 8 часов для реализации. Вы работаете ровно 8 часов в день, и вы не должны оставлять Java-класс незавершенным в конце дня.

Чтобы завершить проект как можно скорее, стратегия состоит в том, чтобы реализовать столько классов, сколько вы можете каждый день. Докажите, что эта жадная стратегия действительно является оптимальной. (Подсказка: пусть ti будет общее количество классов, завершенных в первые i дни, используя вышеприведенную стратегию. Стратегия всегда остается впереди, если ti не меньше, чем общее количество классов, выполненных за первые i дни, используя любую другую стратегию)

Answer 1

Заявление о проблеме является неполным. Нет никаких указаний на то, что любой класс займет менее 8 часов. Поскольку вы не можете оставить какой-либо класс незавершенным, тогда вы должны начать каждый класс в начале дня, чтобы убедиться, что у него есть не менее 8 часов. Поэтому, если C2 действительно занимает 3 часа, а C3 действительно занимает 5 часов, то жадный алгоритм позволит выполнять оба класса в тот же день. Но после того, как C2 займет 3 часа, вам нужно подождать до 3-го дня, чтобы начать C3, чтобы быть уверенным, что у вас есть достаточно времени, чтобы закончить, так как вы не знаете, сколько времени займет C3.

Таким образом, ограничения действительно в конечном итоге диктуют, что усилия будут принимать n дней, 1 день на класс. Таким образом, алгоритм реализации является строго последовательным, а не жадным.

---

Редактировать Ограничения, указанные в проблеме.

(1) Есть п классы Java C1, C2, ..., Cn

(2) эти классы должны быть реализованы в порядке (вы не можете реализовать C2, прежде чем вы закончили C1 и так далее).

(3) Каждый из классов Java занимает не более 8 часов, чтобы осуществить

Но нет никакой оценки для любого класса, с менее чем за 8 часов.

(4) Вы работаете ровно 8 часов в день

(5) Вы не должны оставить класс Java незавершенный в конце дня.

Суть этого (3,4, & 5) - предположим, что я работаю над классом 1 в течение 5 минут. У меня осталось 7 часов 55 минут. Могу ли я начать с Класса 2? Нет, потому что это может занять до 8 часов, и я должен закончить до конца моего 8-часового дня. Поэтому я должен подождать до 2 дня, чтобы начать класс 2 и так далее. Таким образом, реализация строго последовательна и займет n дней, 1 день за класс.

Для использования алгоритма Greedy вам потребуется дополнительная информация.

(6) Вы также знаете, что каждый класс имеет известное количество часов, необходимых для кодирования класса - h1, h2, h3, ..., Hn. Таким образом, класс 1 занимает h1 час, класс 2 занимает h2 часа и так далее. (От 3-го класса не требуется более 8 часов)

Answer 2

Эта проблема аналогична классическому случаю планирования задач, в котором время ожидания в системе должно быть минимизировано.

Пусть C1, C2, ..., C п проецируемого классы и с [1], с [2], ..., с [п] их требуется время реализации. Предположим, вы реализуете C1, C2, ... C n в этом заказе. Таким образом, общее время (ожидание + реализация) для каждого класса C к будет:

с [1] + с [2] + ... + с [к]

Таким образом, мы имеем общее время:

T = п · с [1] + (п - 1) · с [2] + ... 2 * C * [п - 1] + с [п] = сумма (к = 1 до п ) из (п - к + 1) · с [к]

(к сожалению о презентации - надстрочных, подстрочных индексах, и математических уравнениях не поддерживается ...)

Предположим, что времена реализации в нашей перестановке не отсортированы по возрастанию. Таким образом, мы можем найти два целых числа а и Ь, что < б с с []>с [б].Если мы включаем их в расчет T, мы имеем:

T» = (п - + 1) · с [б] + (п - б + 1) · с [] + сумма (к = 1 до п исключением , б) из (п - к + 1) · с [к]

Мы, наконец, вычислить T - Т»:

Т - T ' = (n - a + 1), (с [] - с [б]) + (п - б + 1) (с [б] - с []) = (б - ) (с [] - с [б])

После нашей первоначальной гипотезы (в < б и с []>с [б]), мы имеем б - > 0 и c [a] - c [b]> 0, а, следовательно, T - T»> 0.

Это доказывает, что мы уменьшаем общее время ожидания путем включения любой пары задач таким образом, что чем короче один делается первым.

Ваша постановка проблемы такая же, за исключением того, что перед началом внедрения нового класса вы должны проверить, следует ли вам начинать его сейчас (если на сегодняшний день осталось достаточно времени) или завтра. Но принцип, доказанный здесь, имеет место, когда дело доходит до минимизации общего времени ожидания.

Answer 3

Это не вопрос программирования для SO.Проблема заключается в том, что не требуется решение для кодирования, а скорее доказательство того, что жадный является оптимальным. Что можно сделать с доказательством от противоречия (без сомнения, преподавал в классе до середины).

Что вы хотите сделать, так это рассчитать общее время, затраченное жадным (есть только одно решение), и опровергнуть, что любые свопы в день приведут к лучшему решению. Вы, вероятно, также должны добавить что-то, что упоминает, как обмен может позволить переупорядочить заказ оптимальному решению, если он существует.

Я собирался написать некоторые формулы, но я понимаю, что у Джеффа Морина уже есть уравнения, просто идущие в противоположном направлении. Я думаю, что начинать с жадного решения можно было бы легче объяснить, так как «по порядку» в значительной степени определяется проблемой, и вы можете только сдвинуть работу + - в этот день ее сделать.