Доказательство оптимальности жадного алгоритма

Question

Проблема Я наткнулся на это следующим образом:

Мы имеем п задачи с l_i и w_i быть время и вес задачи i завершения. Придумайте алгоритм, который минимизирует sum for all i of f_i * w_i, где f_i - это время, когда задача i была закончена. Если, например, некоторая задача i запланирована сначала, то f_i = t_i, а затем вторая, а затем f_i = t_i + t_(first task).

я провел некоторое время на это, я сначала подумал, что просто делает список задач, выбирая задания от старшего веса до самого низкого веса будет достаточно хорошо, но понял, что это неправильно, например, если у нас есть 2 задачи:

1 задача: w_i = 10, l_i = 100

2 задача: w_i = 9, l_i = 1

, если мы выбрали один с w_i 10 первого, то мы получили бы 10 * 100 + 9 * 101 = 1909, но если мы выбрали его второй мы получим 9 * 1 + 10 * 101 = 1019.

Теперь я думаю, что оптимальный алгоритм - это тот, который планирует задачи с самого высокого отношения w_i/l_i к самому низкому, но я не уверен, как это доказать. Может ли кто-нибудь помочь с этим?

Answer 1

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

L1W1 + (L1 + L2) W2 - [L2W2 + (L2 + L1)) W1] и обнаружив, что вы увеличиваете, изменив порядок, если L1/W1 и L2/W2 сравниваются в неправильном направлении.

Answer 2

Вы правы, задачи должны быть запланированы в порядке убывания w_i/L_i. Проверьте объяснение доказательства правильности данного профессор Тим Роугарден Part 1 part 2