Задача 8.
Задан массив М [1:N] натуральных чисел, упорядоченный по неубыванию, т.е.: M[1]<=M[2]<=...<=M[N].
Написать алгоритм выплаты заданной суммы S минимальным количеством купюp достоинством M(1), ..., M(N).
|
Решение задачи 8.
Решается аналогично задаче 7. При этом достаточно завести массивы
var A, KOL, PredSum, B: array [0..P] of byte;
Назначение массива A - как и в предыдущей задаче. Массив В служит для временного хранения предыдущих сумм. Элементы KOL[i] и PredSum[i] указывают соответственно минимальное количество элементов, участвующих в получении суммы со значением i и предыдущую сумму, из которой была получена добавлением одного слагаемого сумма i. Формирование этих массивов осуществляется параллельно с заполнением массива А. Сначала
A[0]=1, A[i]=0 для всех i>0,
KOL[0]=0, KOL[i]=254, для всех i>0, (считаем, что если KOL[i]=254, то сумму i набрать нельзя),
PredSum[i]=0 для всех i>0;
for i:=1 to N do {цикл по всем купюрам}
begin
for j:=M[i] to P {цикл по всем возможным суммам с участием купюры M[i]}
if (A[j-M[i]]<>0) and{если можно набрать сумму j-M[i]}
(KOL[j]>KOL[j-M[i]]+1) {и добавлением купюры M[i] мы получаем сумму j из меньшего количества купюр}
then begin
KOL[j]:=KOL[j-M[i]]+1 {то запоминаем это новое количество и в B[j] заносим новую}
B[j]:=j-M[i];{информацию о предыдущей сумме}
A[j]:=1;{и помечаем, что сумму j набрать можно} end
else B[i]:=PredSum[j]; {иначе дублируем старую информацию} for j:=M[i] to P do {Дублируем информацию из B}
PredSum[j]:=B[j]; {в PredSum}
end;
Почему мы не можем непосредственно записывать новую информацию о предыдущей сумме в массив PredSum? Обратите внимание, что массивы A и KOL дублируют друг друга. Напишите тот же фрагмент программы, объединив функции массивов A и KOL в одном массиве A. После завершения работы предыдущего фрагмента если A[S]=1, то сумму S набрать можно с помощью KOL[S] купюр. Предыдущая сумма (до добавления последней купюры) была S'= PredSum[S], следовательно последняя купюра есть S-PredSum[S]. Аналогично выписываем купюры, требуемые для представления суммы S' (используя PredSum[S']).
|
