Глава что такое комбинаторика. Основные проблемы изучения комбинаторики

Задача о рюкзаке. Имеется n наименований товара, причем товар дискретный (его можно отмерять только целыми единицами, как телевизоры или книги, а не вещественным количеством, как сахар или ткань). Заданы объемы единиц каждого товара b_i и их стоимость c_i. Имеется рюкзак объема B. Требуется подобрать набор товаров, вмещающийся в рюкзак и имеющий при этом максимальную стоимость. Более формально: требуется максимизировать функцию F(X) = c_ix_i при ограничениях G(X) = b_ix_i  B и x_i  0, где i = 1…n.
Задача выглядит более реалистичной в такой, например, формулировке. Пусть b_i – это цена единицы товара в долларах, c_i – ее цена в рублях, а B – имеющаяся сумма в долларах. Тогда это – задача об импортере, который хочет наилучшим образом употребить имеющуюся валюту.
Вся сложность задачи связана с требованием целочисленности x_i. Непрерывный вариант той же задачи тривиален (кстати, как она решалась бы?). Далее будет рассмотрен достаточно эффективный алгоритм решения дискретной задачи о рюкзаке.
Задача о многопроцессорном расписании. Даны m одинаковых процессоров и n независимых задач, каждая из которых может решаться на любом процессоре. Время решения каждой задачи равно t_i, i = 1…n. Как распределить задачи по процессорам таким образом, чтобы выполнение всех задач было завершено в кратчайший срок?
В другой интерпретации это задача о куче камней: требуется так разложить n камней с весами t_i на m куч, чтобы вес самой тяжелой кучи был минимален.
Задача о раскраске графа. Дан неориентированный граф G = (V,E). Требуется каждой вершине графа сопоставить целое число (номер цвета) таким образом, чтобы никакие две смежные вершины не были одного цвета и при этом число использованных цветов было минимально.
Есть много несложных алгоритмов, дающих приближенные решения этой задачи, однако найти точное решение не так просто.
Широко известен вариант задачи о раскраске, в котором задано, что граф планарный (т.е. может быть нарисован на плоскости без пересечений ребер). По-другому это формулируется как задача раскраски карты (никакие две страны, имеющие общий отрезок границы, не должны быть одного цвета). С конца XIX века было известно, что для любой карты достаточно использовать 5 цветов, однако только в 80-х годах XX века удалось доказать, что всегда можно обойтись 4 цветами.