2.2. Аппроксимация с заданной точностью 103
на» остается в наихудшем случае экспоненциальным.
Упражнение 2.2.5. Придумайте входные наборы для алго-
ритма 25 «Рюкзак Немхаузера–Ульмана», на которых он будет
работать экспоненциальное время.
Однако практика использования показала, что на реальных
данных алгоритм 25 «Рюкзак Немхаузера–Ульмана» работа-
ет достаточно хорошо. Объяснение этому будет дано в разде-
ле 3.5.
Если же необходимо застраховаться от возможных «пло-
хих» входных данных, то можно использовать идею алгорит-
ма 24 «Рюкзак-ДинПрог» для эффективного приближенного
решения задачи 13 «Knapsack» с любой наперед заданной точ-
ностью (см. раздел. 2.2.2).
Упражнение 2.2.6. Некоторая торговая сеть решила уско-
рить обслуживание на кассах, по возможности исключив возню
кассиров с копейками. К сожалению, просто «прощать» поку-
пателям «копеечную» часть суммы покупки нельзя — для кон-
тролирующих органов необходимо, чтобы зарегистрированные
на кассе суммы полностью совпадали с полученными деньгами.
К кассе покупатель подходит с корзиной товаров, каждая
строка корзины — тип товара, его цена и количество. На каж-
дый товар, можно давать скидку, но такую, чтобы его цена не
стала ниже его цены в рублях (т. е. если товар стоит 12 рублей
и 34 копейки, нельзя сбросить цену ниже 12 рублей).
Задача — найти алгоритм, который уменьшит цены всех
товаров (при вышеуказанном ограничении), чтобы сумма всей
корзины стала целым числом рублей с одной стороны, а с дру-
гой, чтобы потери для торговой сети были минимальными.
Очевидно, что существует тривиальное допустимое реше-
ние — округлить цены всех товаров, но требуется найти именно
решение с минимальными потерями.
Алгоритм должен работать быстро, за линейное от количе-
ства товаров время — это должен быть мгновенный расчет на