Задача: есть банкомат, в нем имеется ограниченное количество купюр разных номиналов. Пользователь хочет получить на руки сумму S. Если это возможно, необходимо вывести список купюр, которые дают нужную сумму, иначе надо написать, что выдача невозможна.
Например: в банкомате есть купюры: 5×1000 (5 купюр по 1000 р.), 2×500 и 4×100. Необходимо выдать сумму в 2700 р. В этом случае выдача возможна: 2×1000 + 1×500 + 2×100.
В зависимости от того, какие номиналы купюр используются, у задачи есть простое или сложное решение.
Если номиналы купюр такие, что при делении большей купюры на меньшую всегда получается целое число, то для решения задачи подходит «жадный» алгоритм. Например, если номиналы купюр равны 1000, 500 и 100 рублей, то как бы мы их не делили, получаются целые числа (1000 ÷ 500 = 2, 1000 ÷ 100 = 10, 500 ÷ 100 = 5) и этот алгоритм пригоден. Он гарантирует выдачу суммы минимальным числом купюр.
Алгоритм работает так:
- пусть остаток = S
- идем в цикле от самой большой купюры к самой маленькой:
- берем максимально возможное количество текущей купюры так, чтобы не превысить остаток и запас купюр в банкомате
- уменьшаем остаток на сумму взятых купюр
- если в итоге остаток равен 0, то выдача возможна, иначе невозможна
В примере выше, алгоритм будет работать так:
- пусть остаток равен 2700
- рассмотрим купюры в 1000 р. Максимальное количество, которое можно взять, не превышая остаток - 2 штуки. Берем 2 таких купюры и остаток уменьшается до 700 р.
- рассмотрим купюры в 500 р. Берем одну и уменьшаем остаток до 200 р.
- рассмотрим купюры в 100 р. Возьмем две, уменьшим остаток до нуля.
- так как остаток равен нулю, выдача возможна: 2×1000 + 1×500 + 2×100
Однако этот алгоритм не работает с номиналами купюр, которые при делении не дают целых чисел. Например, в банкомате есть купюры 5×500 и 3×200 и надо выдать 600 рублей. Алгоритм, рассматривая купюры по 500, возьмет одну, остаток станет равным 100 и выдать нужную сумму не получится. В такой ситуации придется использовать более сложные алгоритмы.
Суть метода в том, что мы перебираем все возможные комбинации купюр, и на каждом шаге считаем их сумму. Если она совпала с требуемой суммой S, то решение найдено, иначе, если ни одна комбинация не дает требуемую сумму, решения нету.
Например, у нас есть такой запас купюр: 3×1000, 2×500, 3×200. Мы перебираем такие комбинации:
| Комбинация | Примечание |
|---|---|
| 0, 0, 1 | это значит 0×1000 + 0×500 + 1×200 |
| 0, 0, 2 | |
| 0, 0, 3 | |
| 0, 1, 0 | так как комбинации 0, 0, 4 быть не может, мы обнуляем последнюю цифру и увеличиваем предыдущую |
| 0, 1, 1 | |
| ... | |
| 0, 2, 2 | |
| 0, 2, 3 | |
| 1, 0, 0 | так как комбинаций 0, 2, 4 или 0, 3, 0 быть не может, мы переходим к 1, 0, 0 |
| ... | |
| 3, 2, 3 | последняя комбинация |
Общий алгоритм такой:
- в начале берем комбинацию 0, 0, … 0, 1
- если сумма купюр в текущей комбинации равна S, решение найдено
- иначе, берем следующую комбинацию
- если комбинации закончились, значит, решения нету
Алгоритм генерации комбинаций такой. Пусть у нас есть комбинация a1, a2 ... an. Мы хотим получить следующую за ней комбинацию.
- делаем цикл, чтобы переменная i уменьшалась от n до 1:
- увеличиваем ai на 1
- если ai не больше, чем запас данной купюры, выходим из цикла
- иначе обнуляем ai и продолжаем цикл
- если в итоге мы получили комбинацию из одних нулей, значит мы перебрали все возможные комбинации
Этот алгоритм найдет решение, если оно есть, но не гарантирует, что выдача будет минимальным количеством купюр. Чтобы это исправить, надо либо перебирать купюры в обратном порядке (то есть, от [3, 2, 3] к [0, 0, 0] в примере выше), либо найти все подходящие комбинации (а не только первую) и выбрать из них комбинацию с минимальным числом купюр.
Главный недостаток этого алгоритма — он очень медленно работает при большом количестве купюр. Допустим, у нас есть купюры 4 номиналов, каждой купюры по 1000 штук. Тогда нам придется перебрать 1000×1000×1000×1000 = 1 триллион комбинаций. Это займет очень много времени даже на современном компьютере. Как же тогда банкоматы решают эту задачу?
На помощь нам придет динамическое программирование.
Динамическое программирование — это подход, когда задачу сводят к более простым задачам. Например, чтобы определить, можно ли выдать сумму S, имея 1000 купюр, мы сначала изучаем, какие суммы можно выдать, имея 999 купюр. А для этого, в свою очередь, определяем, какие суммы можно выдать 998 купюрами, и так далее, пока не дойдем до нуля купюр. Очевидно, что имея ноль купюр, можно выдать только ноль рублей.
Для начала, выпишем все имеющиеся в банкомате купюры в виде списка, от самых больших к самым маленьким. Пусть длина этого списка равна N. Обозначим номиналы этих купюр переменными a1 ... aN. Если у нас запас купюр составляет 3×1000, 2×500, 3×200, то список получится такой:
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
|---|---|---|---|---|---|---|---|
| 1000 | 1000 | 1000 | 500 | 500 | 200 | 200 | 200 |
В примере выше N = 8, a1 = 1000, a4 = 500.
Далее, введем функцию F(i). Эта функция определяет, какие суммы возможно выдать, имея только первые i купюр из списка. Запись F(2) = [0, 1000, 2000] обозначает, что, имея в наличии первые 2 купюры по 1000 р., мы можем выдать лишь 0, 1000 или 2000 рублей. «Выдать 0 рублей» звучит нелогично, но это нужно для работы алгоритма.
При i = 0, то есть, имея ноль купюр, мы можем «выдать» лишь 0 рублей. Нетрудно посчитать значение функции при i = 1, 2, 3:
F(0) = [0]
F(1) = [0, 1000]
F(2) = [0, 1000, 2000]
F(3) = [0, 1000, 2000, 3000]
Теперь попробуем определить, как найти F(i), если мы знаем F(i - 1). Например, чему равно F(4), если мы знаем F(3)? Что поменяется, если к трем купюрам в 1000 р. мы добавим купюру в 500 р.?
Получается два варианта:
- мы можем не использовать новую купюру в 500 р., и тогда мы можем выдать те же суммы, что и раньше: 0, 1000, 2000, 3000
- мы можем добавить эту купюру к любой из ранее имевшихся сумм, и получатся суммы 500, 1500, 2500, 3500
Объединяя два списка, мы получим, что F(4) = [0, 1000, 2000, 3000, 500, 1500, 2500, 3500].
Обобщая, мы можем написать: чтобы вычислить F(i), надо объединить два списка: исходный список значений F(i - 1) и список значений F(i - 1), к каждому значению которого прибавлен номинал купюры ai.
Используя это правило, мы можем написать программу, которая последовательно рассчитывает значения функций F(0), F(1), … до F(N). На каждом шаге мы смотрим получившиеся списки сумм, и если там есть искомая сумма S, то выдача возможна. При этом, чтобы экономить память, мы можем отбрасывать все значения функции F(i), которые больше, чем S.
Оценим сложность алгоритма. Мы вычисляем значение функции от F(1) до F(N), то есть делаем N шагов. На каждом шаге мы работаем с массивом значений, в котором может быть не более S + 1 значений (суммы больше S мы отбрасываем). Получается, в процессе решения мы сделаем примерно N × S шагов. Если у нас 4 вида купюр по 1000 штук (то есть N = 4000) и суммы не превышают S = 10000, то мы сделаем 4000×10000 = 40 000 000 шагов, что гораздо лучше, чем триллион шагов, которые требует алгоритм перебора всех комбинаций.
Если вы хотите поломать голову, то можете попробовать начать писать программу. Если же идей нет, то далее я опишу готовый алгоритм.
Чтобы найти решение, мы будем вычислять значения функции F(i) при i от 0 до N, начав с набора в 0 купюр и добавляя на каждом шаге одну новую купюру. Для того, чтобы хранить список сумм, которые можно выдать на текущем шаге, заведем массив $sums. В ключе этого массива мы будем хранить сумму, а в значении - величину купюры, добавлением которой была получена эта сумма. В начале массив хранит результат F(0) и выглядит так:
| Ключ | Значение |
|---|---|
| 0 | 0 |
Ноль слева значит, что мы можем выдать лишь сумму в 0 рублей, а 0 справа обозначает, что мы не добавляли никаких купюр. Теперь вычислим F(1). Добавим купюру a1 в 1000 рублей. Массив примет вид:
| Ключ | Значение |
|---|---|
| 0 | 0 |
| 1000 | 1000 |
Это значит, что мы можем выдать суммы в 0 и 1000 рублей. 1000 в правой колонке значит, что сумма в 1000 рублей получилась добавлением купюры a1 (1000) к сумме 0 рублей.
Вычислим F(2), а после нее F(3), добавив купюры a2 и a3. Массив примет вид:
| Ключ | Значение |
|---|---|
| 0 | 0 |
| 1000 | 1000 |
| 2000 | 1000 |
| 3000 | 1000 |
Теперь вычислим F(4), добавив купюру a4 в 500 рублей. Для этого мы берем все существующие ключи из массива, добавляем к ним 500, и, если такого ключа нет, создаем его, записывая справа 500:
| Ключ | Значение |
|---|---|
| 0 | 0 |
| 500 | 500 |
| 1000 | 1000 |
| 1500 | 500 |
| 2000 | 1000 |
| 2500 | 500 |
| 3000 | 1000 |
| 3500 | 500 |
Так мы делаем, пока искомая сумма S не появится в колонке слева. Если же мы сделали N шагов, использовали все купюры, а сумма S так и не появилась, то ее нельзя выдать.
Цифры в колонке слева показывают, какие суммы возможно выдать, а цифры в колонке справа позволят нам определить, какими именно купюрами это можно сделать. Например, мы хотим выдать сумму в 2500. Так как она есть в колонке «ключ», ее возможно выдать. Чтобы определить, какими купюрами она выдается, мы смотрим в правую колонку. Там стоит 500. Значит, мы берем одну купюру в 500 (остается 2000) и переходим к строчке с ключом 2000. Там справа стоит 1000, значит мы берем купюру номиналом в 1000 (остается 1000) и переходим к строке с ключом 1000. Там тоже стоит 1000, мы берем эту купюру и в остатке остается ноль. Значит, 2500 можно выдать купюрами 500 + 1000 + 1000.
Теперь вы можете написать решение задачи и сравнить его с написанным ниже.
Итак, вот алгоритм:
- пусть
$sэто сумма, которую надо выдать - пусть
$nэто суммарное количество купюр - преобразуем запас купюр в список
$a[1 ... n], в списке купюры идут по убыванию - создадим массив
$sumsи добавим в него строчку с ключом и значением 0. Это соответствует значению F(0) = [0]. - делаем цикл по
$iот 1 до N:- // в массиве
$sumsмы имеем значение функции F(i - 1), и теперь по нему вычисляем F(i). Мы добавляем купюру ai к имевшимся ранее. - пусть номинал добавляемой купюры
$value=$a[$i] - создаем пустой массив
$newSums. Он будет хранить новые суммы, которые получаются добавлением текущей купюры$valueк старым суммам - обходим все ключи массива
$sums. Для каждого ключа$sum:- вычисляем
$newSum=$sum+$value - если
$newSum>$s, пропускаем шаг цикла. Незачем тратить память на хранение больших сумм. - если в
$sumsнет ключа$newSum, то добавляем ключ$newSumв массив$newSumsсо значением$value
- вычисляем
- добавляем значения из
$newSumsв$sums. Для этого можно использовать оператор$sums += $newSums - если в
$sumsесть ключ$s, выходим из цикла - мы уже получили требуемую сумму
- // в массиве
- если в
$sumsнет ключа$s, выдать сумму невозможно - иначе, сумму выдать возможно. Осталось лишь определить, какими купюрами
- пусть невыданный остаток
$rem=$s - пока
$remбольше нуля:- смотрим значение
$sums[$rem]и берем купюру такого номинала - уменьшаем
$remна величину взятой купюры
- смотрим значение
Мы добавляем значения в отдельный временный массив $newSums, а не напрямую в $sums, чтобы не получилось такого, что мы добавили в массив новое значение (1000 + 500 = 1500), а потом взяли его и добавили к нему ту же самую купюру еще раз (1500 + 500 = 2000).
Купюры идут в списке по убыванию для того, чтобы первыми рассматривались варианты выдачи более крупными купюрами, то есть меньшим числом купюр.
Задача о грабителе — это аналог задачи про банкомат и она имеет похожее решение. Грабитель проник в банк и увидел там N золотых слитков весом w1, w2 … wN кг. Вес каждого слитка — целое число килограмм. В его рюкзак помещается не более K килограмм. Какие слитки он должен взять, чтобы унести максимальное количество золота?
Если пытаться решить эту задачу полным перебором, то возможных комбинаций будет очень много. Допустим, у нас есть 100 слитков. Каждый слиток можно либо взять, либо не брать. Всего будет 2×2×…×2 = 2100 ≈ 1030 (то есть, единица с 30 нулями) вариантов выбора. Это называется "NP-сложность" - сложность решения нельзя представить многочленом.
Если же использовать динамическое программирование, эта задача решается за разумное время (за N×K шагов). Попробуйте решить её, используя описанный выше подход.
И задача про банкомат, и задача про грабителя являются частными случаями более общей задачи об укладке рюкзака. Эта задача известна математикам более 100 лет и формулируется так: есть N предметов, каждый предмет имеет вес wi и цену pi, и есть рюкзак вместимостью K килограмм. Какие предметы нужно положить в рюкзак, чтобы их стоимость была максимальной?
Эта задача исследована. Если вес и цена предметов - целые числа, то ее можно решить методом динамического программирования. Если же вес и цена могут быть дробными, то оптимальное решение задачи неизвестно. Это значит, что нам придется перебирать все 2N возможных комбинаций.
Подробнее про динамическое программирование и задачу о рюкзаке можно прочесть тут:
- Другие примеры задач, которые решаются динамическим программированием
- в Википедии можно прочесть об истории задачи и ее подвидах