Disjoint Set Forest для планирования заданий

Question

Как я могу использовать непересекающиеся наборы леса для планирования заданий с штрафами, чтобы штрафы были минимизированы?

Мы могли бы сначала расположить рабочие места в порядке убывания на основе их штрафов. Каждый узел x леса будет представлять номер задания, а значение rank[x] будет представлять его штраф. Но как я могу минимизировать это значение ранга [x], чтобы минимизировать штрафы? Порядок узлов даст мне порядок заданий, но какой будет алгоритм для этого? Как мне сделать лес?

Answer 1

Ваша проблема исходит от CLRS 16-4? В последнее время я тоже делаю это упражнение.
Получив некоторые подсказки от обсуждения с моими друзьями, я наконец нашел похожие посты в Интернете. Два сообщения находятся в блоге CSDN людьми, разделяющими их коды.
Прочитав их посты, я думаю, что их посты действительно помогают понять, как использовать Disjoint Set Forest для решения задачи планирования заданий. Надеюсь, они тоже могут вам помочь.
Два сайта
http://blog.csdn.net/hechenghai/article/details/6844356 http://blog.csdn.net/jxy859/article/details/6615119

Answer 2

Я тоже сейчас нахожусь на этой проблеме, и я нашел эту записку лекции, может быть, это поможет. PS Хотя этому посту уже год, это может помочь другим, кто сталкивается с той же проблемой.