Задача 7.
У покупателя есть n монет достоинством H(1),..., H(n). У продавца есть m монет достоинством B(1),...,B(l). Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача (если она необходима).
|
Решение задачи 7.
Если S>H(1)+...+H(n), то сумму выплатить нельзя.
Если покупатель отдаст все свои купюры продавцу, то понятно, что для решения исходной задачи надо определить, может ли продавец вернуть сумму H(1)+...+H(n)+B(1)+...+B(l)-S, используя любые имеющиеся теперь у него купюры M[i] (его и покупателя). Для этого удобно отсортировать купюры согласно их достоинства в порядке неубывания.
Пусть P=M[1]+M[2]+ ... +M[n+l].
Решим чуть более общую задачу: найдем все непредставимые данными купюрами суммы на промежутке от 0 до P.
Заведем массив A[0 .. P] натуральных чисел. Элемент A[i]=1, если мы можем выплатить сумму i (т.е. существует набор купюр суммарного достоинства i), и A[i]=0 иначе.
Будем строить всевозможные суммы, используя последовательно 0,1,2,...,N купюр.
Очевидно, что сумма из ноля купюр - это ноль, поэтому сначала A[0]=1.
Предположим, что мы нашли всевозможные суммы, которые можно составить, используя не более (k-1) - ой купюры M[1], ..., M[K-1]. Добавим еще одну купюру M[k].
Теперь мы можем выплатить следующие суммы:
1) Все суммы, которые можно было составить с помощью купюр M[1], ... , M[K-1].
2) Все суммы, которые можно было составить с помощью купюр M[1], ... , M[K-1], увеличенные на M[K].
Расстановка новых пометок в массиве A может выглядеть следующим образом:
for i:=P-M[K] downto 0 do
if A[i]=1
then A[i+M[K]]:=1;
Мы проходим по массиву справа налево для того, чтобы не использовать повторно впервые образованную на данном шаге сумму.
После выполнения n+l шагов алгоритм заканчивает работу.
Если известно, что H(1)+...+H(n)+B(1)+...+B(l)-S не превосходит некоторой константы D, то тогда массив A имеет смысл брать не из P, а из D элементов.
|
