|
#1
|
|||
|
|||
Жадный алгоритм
Подскажите как нибудь,или подкиньте часть программы,или весь алгоритм,не понимаю задачу
Программисту дано n заданий. У каждого задания известен свой дедлайн( последний день выполнения), а также его стоимость (то есть если он не выполняет это задание, то он теряет столько-то денег). Программист за один день может сделать одно задание. Выполнение задания можно начать с момента 0. Нужно максимизировать прибыль. Разбор: Выгодно делать самые «дорогие задания», а наименее дорогие можно и не выполнять — тогда прибыль будет максимальна. Возникает вопрос: каким образом распределить задания? Будем перебирать задания в порядке убывания стоимости и заполнять расписание следующим образом: если для заказа есть еще хотя бы одно свободное место в расписании раньше его дедлайна, то поставим его на самое последнее из таких мест, в противном случае в срок мы его не можем выполнить, значит поставим в конец из свободных мест. |