Изменения

<tex dpi = "200">1 \mid r_jr_i, p_j p_i = p \mid \sum{w_j C_jw_i C_i}</tex>

{{Задача|definition=Дано n работ и 1 станок. Для каждой работы известны время появления r_i, вес w_i и дедлайн d_i. Время выполнения всех работ p_i равно p. Требуется выполнить все работы так, чтобы значение sum(w_iC_i), где C_i — время окончания работы, было минимальным.}} <tex dpi = "200">1 \mid r_jr_i, p_j p_i = p \mid \sum{T_jT_i}</tex> {{Задача|definition=Дано n работ и 1 станок. Для каждой работы известны время появления r_i, вес w_i. Время выполнения всех работ p_i равно p. Требуется выполнить все работы так, чтобы значение sum(T_i) — суммарной медлительности работы(T_i = max(C_i - d_i), 0) — было минимальным.}} ==Предисловие== Аналогично задаче [[1ripipsumwu|<tex>1 | r_i, p_i = p | \sum{w_i U_i}</tex>]], данные задачи решаются при помощи динамического программирования. Вместо критериев оптимизации <tex>\sum{w_i C_i}</tex> и <tex>\sum{T_i}</tex> возьмём более общую для них функцию вида <tex>\sum{f_i(C_i)}</tex>, где функции <tex>f_1,...,f_n</tex> обладают следующими свойствами: * <tex>f_i</tex> не убывает для всех <tex>j = 1,...,n</tex>; * <tex>f_i - f_j</tex> не убывает для всех <tex>i, j = 1,..., n</tex> при <tex>i < j</tex>. Функции <tex>\sum{w_i C_i}</tex> и <tex>\sum{T_i}</tex>удовлетворяют данным условиям, если отсортировать работы так, что <tex>w_1 \geq w_2 \geq ... \geq w_n</tex> и <tex>d_1 \leq d_2 \leq ... \leq d_n</tex>. ==Алгоритм== ==Время работы== ==Корректность алгоритма== ==Другие задачи== ==Источники информации==