Алгоритм выделения работы с динамическим программированием

Question

Проблема заключается в следующем:

Необходимо выполнить n заданий, каждое из которых характеризуется усилением {v1, v2 ,. , , , vn}, время, необходимое для его реализации {t1, t2 ,. , , , tn} и крайний срок его реализации {d1, d2 ,. , , , dn} с d1 <= d2 <= ..... <= d3. Зная, что выигрыш происходит только в том случае, если работа выполняется к тому времени, и что у вас есть одна машина. Необходимо описать алгоритм, который вычисляет максимальный коэффициент усиления, который можно получить. </p>

Я думал о рекуррентном уравнении с двумя параметрами, один из которых указывает на i-ую работу, а другой показывает момент, в который мы реализуем: OPT (i, d), если d + t_i <= d, то добавляется получить t_i. (тогда вариант множественного выбора .. это мин для 1 <= i <= n). </p>

Моя главная проблема: как мне найти работу, которая ранее выполнялась? Я использую структуру данных поддержки?

Как бы вы написали уравнение повторения?

спасибо тебе !!!!

Answer 1

Моя главная проблема: как мне найти работу, которая ранее выполнялась?Я использую структуру данных поддержки?
Хитрость в том, что вам не нужно знать, какие задания уже выполнены.Потому что вы можете выполнять их в порядке увеличения срока.

Допустим, какое-то оптимальное решение (с максимальной прибылью) требует от вас выполнения задания A (срок исполнения 10), а затем задания B (срок 3).Но в этом случае вы можете смело менять местами A и B.Они оба все равно будут завершены вовремя, и новая договоренность принесет одинаковую общую прибыль.
Конец доказательства.

Как вы написали бы уравнение повторения?
У вас уже есть общее представление, но вам не нужен цикл ( мин для 1 <= i <= n </em>).

max_profit(current_job, start_time)
    // skip this job
    result1 = max_profit(current_job + 1, start_time)

    // start doing this job now
    finish_time = start_time + T[current_job]
    if finish_time <= D[current_job]
        // only if we can finish it before deadline
        result2 = max_profit(current_job + 1, finish_time) + V[current_job];
    end

    return max(result1, result2);
end

Преобразование его в DP должно быть тривиальным.

Если вам не нужна сложность O(n*max_deadline) (например, когда значения d и t велики), вы можете прибегнуть к рекурсии с memoization и сохранить результаты в хеш-table вместо двумерного массива.

edit
Если все работы должны быть выполнены, но не все будут оплачены, проблема остается той же.Просто сдвиньте задания, на которые у вас нет времени (задания, которые вы не можете выполнить до истечения срока), до конца.Вот и все.

Answer 2

Я прочитал верхние комментарии и понял, что вы не ищете эффективность, которую вы ищете для завершения, так что это убирает прибыль с пути и оставляет нам просто упорядочение в срок.Это классическая задача, выполненная Divide et Impera Quicksort http://en.wikipedia.org/wiki/Quicksort

Answer 3

Прежде всего, я бы выбрал предметы с наибольшей доходностью. Смысл работы, которые имеют самая большая скорость в значении / времени, которая может соответствовать их крайнему сроку (если сейчас + t1 превышает d1, то это фальшивка). После этого я проверяю время между now + job_time и каждым крайним сроком, получая «шанс закончить» для каждой работы. Работы, которые придут первыми, будут работать с наибольшей доходностью и наименьшим шансом закончить. Идея состоит в том, чтобы выжать самые ценные рабочие места. СЛУЧАИ:

Если для задания с доходностью 5 требуется 10 секунд, а срок его выполнения наступает через 600 секунд, а для задания с таким же доходом требуется 20 секунд, а срок - через 22 секунды, тогда я запускаю вторую.

Если для задания с доходностью 10 требуется 10 секунд, а срок его выполнения наступает через 100 секунд, в то время как для другого задания с доходностью 5 нужно 10 секунд, а срок - через 100 секунд, я выполню первый один.

Если их доходность идентична, и они требуют того же времени, чтобы закончить, в то время как их крайний срок наступает через 100 секунд, соответственно 101 секунду, я запусту первый, так как он выигрывает больше времени.

.. и так далее и тому подобное ..

Рекурсия в этом случае относится только к переупорядочению заданий по этим параметрам с помощью «Выход» и «Шанс завершить».

Не забудьте всегда увеличивать «сейчас» (+ job_time) после вставки работы в заказ. Надеюсь, что он отвечает.