Задача о багажнике. Вам нужно перевезти в багажнике автомобиля коробки разных размеров. Задача требует отобрать те коробки, при укладке которых останется меньше всего неиспользованного пространства. Как выясняется, никакого рационального алгоритма, позволяющего выбрать оптимальное сочетание коробок, исходя из их размеров, не существует. Предположим, что все коробки имеют одинаковую высоту и ширину, которые точно совпадают с внутренними размерами багажника, но разную длину. Длина багажника – 150 см, а длина имеющихся в вашем распоряжении коробок равна 16, 27, 37, 42, 52, 59, 65 и 95 см. Есть ли какой-нибудь удобный способ выбрать такое сочетание коробок, которое заполнит багажник с наименьшими потерями?

Задача о расписании уроков. В начале каждого учебного года каждая школа сталкивается с задачей составления расписания для учеников. Но у возможностей распределения занятий по расписанию есть ограничения, связанные с тем, какие предметы выбирает каждый из учеников. Поскольку Ада решила заниматься химией и музыкой, уроки по этим предметам нельзя назначать на одно и то же время. А Алан выбрал химию и киноведение. Но в день может быть всего восемь уроков. Школе нужно каким-то образом втиснуть в расписание все предметы так, чтобы ни у кого не было нескольких уроков в одно и то же время. С учетом всех этих ограничений составление расписания иногда бывает похоже на укладку ковра в комнате с не вполне подходящими размерами. Не успеешь уложить ковер в одном углу, как он вспучивается в другом. Еще это похоже на решение судоку: казалось бы, все числа наконец оказались на нужных местах, как вдруг обнаруживается, что в одной из строк стоят две двойки. Черт!

Судоку. Если вы уже пытались решить какие-нибудь из самых трудных вариантов этой японской головоломки, вам случалось попадать в ситуации, в которых, по-видимому, остается только выбрать следующее число наудачу, а затем разбираться с логическими следствиями из этого решения. Если это решение было неверным и приводит к противоречию, вам остается только вернуться к тому шагу, на котором вы его приняли, и попытаться пойти по другому пути.

Задача о званом ужине. Проблема, сходная с задачей о расписании уроков, возникает, когда вы хотите пригласить друзей на ужин, но некоторые из них не ладят друг с другом, и вы не хотите приглашать их на один и тот же ужин. Чтобы определить минимальное количество ужинов, на которых у вас побывают все, но так, чтобы ни на одном из них не встретились те, кто не хочет встречаться, необходимо перебрать все возможные комбинации приглашенных.