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