Жадность

1. [Сережа.K] Сортировки
1. Унести в рюкзаке максимальное число вещей. Sort w_i ↑
2. Выполнить как можно больше заказов. У каждого есть time_i. Sort time_i ↑
3. Выполнить все заказы. У каждого есть deadline_i и time_i. Sort deadline_i ↑
4. Непрерывный рюзкзак с весами и стоимостями (дискретный ∈ NP-hard). Sort value_i/weight_i ↑
5. Есть работы, t_i, fee_i, время выполнения − T_i. Минимизировать ∑ fee_iT_i (сортировка по частному). Версия этой задачи с древовидными зависимостями.
6. Задача про 2 станка: автоматический компаратор, правильный компаратор
7. Построить башенку из всех коробок. У каждой есть масса m_i и прочность s_i. Sort m_i + s_i ↓
8. Сконкатенировать все строки так, чтобы результат был минимален
2. [Сережа.K] Коробки и то, что из них следует
1. Построить башенку из максимального числа коробок. У каждой есть масса m_i и прочность w_i. Sort m_i + w_i ↓
1. Решение динамика за O(n²) (отсортировали по d_i, T[i, k] − min, где k − сколько из первых i мы взяли)
2. Другое решение за O(n²) (отсортировали по t_i, пытаемся добавить)
3. Жадное решение с деревом отрезков (min, +=) за O(nlogn) (тут же рассказывается доказательство предыдущего: пытаемся удалить минимальный t_i и перейти к подзадаче)
4. Жадное решение с set за O(nlogn) (в порядке d_i пытаемся жадно добавить или заменить)
2. Аналогичные задачи
1. Скобочные последовательности (разбор разных знаков руками, при фиксированном знаке пользуемся теорией)
2. Школьники на РОИ вылезают из ямы (эквивалентна коробкам)
3. [skipped] Авторитеты
3. [Сережа.K] Жадность и перебор на примере задачи о гамильтоновом пути
1. Перебор
2. Перебор с отсечениями (например, с запоминанием, т.е. динамика)
3. Перебор с эвристикой минимальной степени
4. Жадность!
5. Жадность можно запускать несколько раз с random_shuffle