Расчет сдачи

В задаче о восьми ферзях мы сначала искали единственное решение поставленной задачи, затем находиди все возможные решения. Теперь попробуем заняться поиском оптимального решения. Для этого необходимо оставлять одно решение, в определенном смысле оптимальное:

if f(решение) > f(оптимальное) then оптимальное:=решение.

Где в переменной {\it оптимальное} хранится лучшее из полученных к этому времени решений. Значение f(оптимальное) удобнее хранить еще в одной переменной (или массиве), чтобы избежать частого его перевычисления.

В качестве примера рассотрим задачу рассчета сдачи при покупке товаров в магазине. Нужно найти, руководствуясь некоторыми ограничениями, оптимальную выборку из заданного множества объектов. В нашем случае

оптимальным явлется выборка купюр большего достоинства, чтобы выдать сдачу с помощью наименьшего количества купюр (бумажных денег).

Итак, задача. Магазин оборудован кассовыми аппаратами, которые работают следующим образом. Кассир

набирает на клавиатуре кассового аппарата стоимость каждого купленного предмета (либо считывает штрих-код),

аппарат же постепенно накапливает суммарную стоимость. Затем кассир набирает на клавиатуре сумму денег, данную покупателем. Аппарат должен подсчитать сумму сдачи и определить, какие купюры и в каком колличестве образуют эту сумму.

Предпочтение отдается купюрам большего достоинства, что обычно приводит к уменьшению числа купюр, входящих в сдачу.

Имеются купюры достоинством в 10, 20, 50, 100, 500, 1000, 5000, 10000, 20000, 50000 и 100000.

Кроме того, в кассовом аппарате имеются отделения для каждого типа монет, и при сдаче нужно учитывать наличие купюр в том или ином отделении.

Процедура Popytka описывает процесс исследования возможности выдать сдачу — она вызывается рекурсивно (для исследования очередного i-го набора купюр: i=1, 2, …, n) до тех пор, пока все они не будут рассмотрены.

Procedure Popytka(i:integer);

begin

if включение приемлемо

(наличие купюр: дать сдачу таким набором возможно) then begin включение i-го набора купюр;

 if i<n then  Popytka(i+1) else проверка оптимальности;

исключение i-го набора купюр

end;

if приемлемо невключение

(не хватает купюр такого достоинства, давать сдачу таким набором нельзя) then

 if i<n then  Popytka(i+1) else проверка оптимальности;

end

end; {Popytka}

Из такой схемы видно, что всего $2^n$ возможных выборок купюр, поэтому нужно использовать такой критерий приемлимости, который бы значительно сократил число перебираемых кандидатов на правильное решение. Для пояснения этого процесса возьмем кон

Пусть каждый из n наборов купюр характеризуется количеством купюр одного достоинства и ценностью (достоинством купюры)(например, 2 купюры по 1 тыс., 3 купюры по 100 руб.,\dots)

Оптимальной назовем выборку с максимальной ценностью и меньшим количеством. (из набора 5 купюр по 100 руб. и 1 купюра в 500 руб. выбираем 1 купюру в 500 руб.)

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

У нас получаются такие описания:

type indeх=1..n;

object_= record kolichestvo, dostoinstvo: integer end;

var obj: Array[index] of object_;

max_kolichestvo, summa_sdachi: integer;

kupiyry:Array[(10, 20, 50, 100, 500, 1000, 5000, 10000, 20000, 50000, 100000)] of integert;

sdacha, optim_sdacha: set of index;

Переменная max_kolichestvo соответсвует максимальному количеству купюр того или иного достоинства,

имеющихся в наличии, summa_sdachi — сумма сдачи, sdacha, optim_sdacha — наборы купюр (очередной и оптимальный к данному моменту), которыми сдача может быть выдана.

{\bf Упражнение.} Напишите вариант

программы, определяющей оптимальный набор купюр при сумме сдачи, вводимой с клавиатуры.

При распечатывании варианта сдачи можно воспользоваться оператором сase:

\begin{alltt}

case NN of

50: writeln(‘пятьдесят рублей’)

100: writeln(‘cто рублей’);

1000: writeln(‘тысяча рублей’);

Для тех, кому это упражнение покажется сложным, приведем рассуждения Дьердь Пойа, который популяризовал похожую задачу, в которой вместо купюр были монеты достоинством 1, 5, 10, 25 и 50, для простоты, копеек.

Запишем бесконечную сумму, представляющую все возможные способы размена, для начала, 1-копеечными монетами:

$Kop=no_kop+\copyright +\copyright\copyright +\copyright\copyright\copyright +\copyright\copyright\copyright\copyright +…

=no_kop+\copyright+\copyright ^2+\copyright ^3+\copyright ^4+…$

%no_kop — нет ни одной монеты достоинством в 1 копейку — можно сделать перечеркнутую монету или 1

%\copyright — вместо этой последовательности предполагается сделать рисунок монеты с цифрой 1 посередине

%\copyright ^4 — монетка «в 4-й степени»

%^ — знак степени

Первое слагаемое обозначает вариант не заплатить ничего, второе — заплатить одну копейку, третье — две и т.д.

Если для размена мы используем «пятаки», то суммой всех возможных способов будет:

$Pyat=Kop+Kop\bigdot +Kop\bigdot\bigdot +Kop\bigdot\bigdot\bigdot +Kop\bigdot\bigdot\bigdot\bigdot +…

=(no_pyat+\bigdot +\bigdot ^2+\bigdot ^3+\bigdot ^4+…)Kop,$

поскольку каждый вариант выплаты включает некоторое количество пятаков, выбираемых из первого множителя, и некоторое количество 1-копеечных монет, выбираемых из $Kop$.

Аналогично, добавляя 10-копеечные монеты, получим бесконечную сумму

$Dec=(\no_dec +\dec +\dec ^2+\dec ^3 +\dec ^4+…)Pyat$.

При добавлении еще и 25-копеечных и 50 -копеечных монет:

$Dv_pyat=(\no_dv_pyat +\dv_pyat +\dv_pyat ^2+\dv_pyat ^3+\dv_pyat ^4+ …)Dec$

$Pyat_dec=(\no_pyad_dec+ \pyad_dec +\pyad_dec ^2+\pyad_dec ^3+\pyad_dec ^4+…)Dv_pyat$

Последняя сумма, если ее полностью раскрыть, будет содержать слагаемые вида

«не платить ничего», koeff\pyad_dec ^a\dv_pyat ^b\dec ^c\bigdot ^d\copyright ^e — любые варианты наборов монет разных достоинств c некоторыми коэффициентами ($\dv_pyat\pyad_dec$=$\pyad_dec\dv_pyat$)

Сколько слагаемых в $Pyat_dec$ стоят, например, ровно 50 копеек?

Задача решается с помощью трюка. Заменим 1-копеечную монету ($\copyright$) на z,

5-копеечную ($\bigdot$) на z^5, 10-копеечную ($\dec$) на z^10, 25-копеечную ($\dv_pyat$) на z^25,

50-копеечную ($\pyad_dec$) на z^50. Каждое слаагаемое тогда заменится на z^n, где n — стоимость исходного слагаемого в копейках (1-копеечных монетах). Например слагаемое \dec ^2\pyat ^2\copyright ^3 превратиться в z^{10+10+5+5+1+1+1)=z^33.

Каждый из возможных способов заплатить 12 копеек — 10 1^2, 5 1^7, 5^2 1^2, 1^12 — сведется к z^12, а коэффициентом при

z^12, поскольку существует 4 возможных способа, будет 4.

Количество способов заплатить сумму в n копеек, используя монеты того или иного достоинства, будет равно

коэффициенту при z^n в соответствующей сумме.

Можно воспользоваться формулой для бесконечной суммы вида 1+z^m+z^2m+… = 1/(1-z^m), тогда

$Kop=1/(1-z)$

$Pyat=Kop/(1-z^5)$

$Dec=Pyat/(1-z^10)$

$Dv_pyat=Dec/(1-z^25)$

$Pyat_dec=Dv_pyat/(1-z^50)$

Умножая на знаменатель, получим

$(1-z)Kop=1$

$(1-z^5)Pyat=Kop$

$(1-z^10)Dec=Pyat$

$(1-z^25)Dv_pyat=Dec$

$(1-z^50)Pyat_dec=Dv_pyat$

Приравнивая коэффициенты при z^n в этих уравнениях, получим рекурентные соотношения, из которых желаемые коэффициенты легко вычисляются :

$Kop_n=Kop_{n-1}+[n=0],$

$Pyat_n=Pyat_{n-5}+Kop_n,$

$Dec_n=Dec_{n-10}+Pyat_n,$

$Dv_pyat_n=Dv_pyat_{n-25}+Dec_n$

$Pyat_dec_n=Pyat_dec_{n-50}+Dv_pyat_n$

(Kop_n, Pyat_n, Dec_n, Dv_pyat_n, Pyat_dec_n — обозначают число способов заплатить сумму в n копеек, если можно использовать монеты не старше 1, 5, 10, 25 и 50 соответственно.)

Получаем, что сдачу, например, в 50 копеек можно выдать 50-ю способами.

{\bf Упражнение.} Напишите вариант

программы, определяющей количество вариантов выдать сдачу, используя монеты определенного достоинства.

 

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

методические материалы по информатике