Введение понятие комбинаторики

Задача о кратчайшем пути в графе. Дан граф G = (V,E) и матрица длин ребер L. Заданы также две вершины A и B. Требуется найти кратчайший путь из A в B.
Это также задача оптимизации. Ее можно рассматривать как задачу фиксированной размерности (для каждого ребра указать, входит оно в кратчайший путь или нет), но, вероятно, более естественно считать размерность нефиксированной (составить список ребер, образующих кратчайший путь). Несмотря на очевидное сходство с предыдущей задачей, задача о кратчайшем пути решается намного легче, для нее в теории графов разработаны очень эффективные алгоритмы.
Задача о длиннейшем пути в графе. В условиях предыдущей задачи требуется найти самый длинный путь из A в B, не образующий циклов.
Как ни странно, эта задача, в отличие от предыдущей, весьма сложна для решения.
Задача о рюкзаке. Имеется 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. Непрерывный вариант той же задачи тривиален (кстати, как она решалась бы?). Далее будет рассмотрен достаточно эффективный алгоритм решения дискретной задачи о рюкзаке.