Жадный алгоритм для k-ограниченных ресурсов

Я изучаю жадные алгоритмы и мне интересно решение для другого случая.

Для задачи выбора интервала мы хотим выбрать максимальное количество работ, которые не конфликтуют друг с другом, поэтому выбор работы с самым ранним временем окончания работает.

Другой пример: у нас есть n заданий, и мы хотим купить как можно меньшее количество ресурсов. Здесь мы можем отсортировать все задания слева направо, и когда мы встречаем новую начальную точку, мы увеличиваем счетчик, а когда мы встречаем конечную точку, мы уменьшаем счетчик. Таким образом, наибольшее значение, которое мы получим из этого счетчика, будет количеством ресурсов, которые нам нужно купить.

Но, например, что если у нас n задач, но k ресурсов? Что если мы не можем позволить себе больше, чем k ресурсов? Каким должно быть жадное решение, чтобы удалить как можно меньше задач, чтобы удовлетворить это?

Также, если есть конкретное название для последней проблемы, которую я написал, я буду рад это услышать.

6
задан 20 October 2011 в 18:26
поделиться