Перебор (5 ноября 2024)

1. Перебор всех перестановок для задачи ∑a_ib_i → max
   1. next_permutation, do..while
   2. рекурсия за n!*n
   3. преимущества над next_permutation: решгаем
   4. рекурсия за n!
   5. Усложнение: чтобы соседние элементы отличались хотя бы на два
   
   
2. Рюкзак
   1. Рюкзак без стоимостей, subsetsum, O(2ⁿ)
   2. Запоминание O(n*S)
   3. Рюкзак со стоимостями, knapsack (ограбление банка), O(2ⁿ)
   4. Смотреть в прошлое, в будущее, возвращать инфу про будущее, O(n*S)
   
   
3. Задача о коммивояжере (развозка пиццы). n! → 2ⁿ*n² (map pair int, vector int)
   
   
4. Задача о разбиении на слагаемые
   1. Сам перебор. За сколько работает? O(Ответа), 2^sqrt(n)
   2. Запоминание на уровне n³.
   
   
5. Задача о замощение доминошками (2^w * w)
   1. Перебор за 2^wh/2
   2. Добавляем map vector vector int → int
   3. Оцениваем как 2^wwh
   
   
6. Задача про расселение студентов (м/д; 1/2/3/4курс; пожелания)
   1. Упрощение (жадность): забить на все сложные, мальчиков подряд, девочек подряд
   2. Жадность + локальные оптимизации (свопаем, пока улучшается)
   3. Перебор за n! (связь с перебором перестановок)
   4. Более умный перебор
   5. Жадность + перебор