Рассмотрим одну задачу, которая на leetcode маркирована как "medium", хотя на самом деле это крайне сложная задача (upd: проницательный @wataruзаметил, что на литкоде решают гораздо более простую задачу). Примечательна она тем, что допускает в разной степени оптимальные решения, самые упрощённые из которых действительно весьма просты, а самые оптимальные ещё не найдены современной наукой. В этой задаче ценно то, что на её примере можно изучать целый ряд техник программирования.
Примеры кода даются на языке Scheme, который я использую для объяснения студентам теоретических основ конструирования программ. Некоторые из примеров можно легко перевести на другие языки программирования. Но мы же не будем публиковать решения задач leetcode на языке, принимаемом leetcode, правильно?
Постановка задачи
У нас имеется банкомат с кассетой, отделения которой заряжены купюрами разных номиналов. Клиент просит банкомат выдать ему определённую сумму. Необходимо найти все варианты выдачи этой суммы минимальным количеством купюр.
Для простоты картины будем считать, что если в каком-то отделении кассеты вообще есть купюры, то их там неограниченно много. Такое допущение принципиально ничего не меняет в решении задачи, но несколько упрощает код.
В отличие от нашей задачи, где требуется найти все варианты выдачи, на leetcode ищут какое-нибудь минимальное решение, или, точнее, его длину. Такая задача требует гораздо меньше вычислений.
Простейший пример
В кассете имеются купюры номиналом 5000, 2000, 1000, 500, 200 и 100 рублей. Просим выдать 6400 рублей, получаем 5000+1000+200+200, решение единственно.
Первый подход к снаряду – жадный алгоритм
Простейшим решением, которое сразу приходит в голову, является жадный алгоритм: выдаём самые крупные купюры, пока это возможно, потом переходим к более мелким и т.д.
В нашем примере:
6400 >= 5000? Да, выдаём 5000. Остаётся 1400.
1400 >= 5000? Нет.
1400 >= 2000? Нет.
1400 >= 1000? Да, выдаём 1000. Остаётся 400.
400 >= 1000? Нет.
400 >= 500? Нет.
400 >= 200? Да, выдаём 200. Остаётся 200.
200 >= 200? Да, выдаём 200. Остаётся 0. Задача решена.
Это решение можно представить следующим кодом на языке Scheme:
(define *купюры* '(5000 2000 1000 500 200 100))
(define (оптимальный-размен сумма)
(жадный-размен сумма *купюры*))
(define (жадный-размен сумма купюры)
(cond
((zero? сумма) '())
((null? купюры) '())
((<= (car купюры) сумма)
(cons (car купюры)
(жадный-размен (- сумма (car купюры))
купюры)))
(else (жадный-размен сумма (cdr купюры)))))> (оптимальный-размен 6400)
(5000 1000 200 200)
Тут у нас, однако, возникают серьёзные проблемы.
Во-первых, жадный алгоритм по своей природе выдаёт только одно решение, а мы хотим получить все.
Во-вторых, это решение может быть неоптимально:
> (define *купюры* '(5000 2000 100))
> (оптимальный-размен 6000)
(5000 100 100 100 100 100 100 100 100 100 100)
Пятёрка сразу захватила слишком много денег, и остаток нам пришлось добирать сотнями, хотя оптимальным решением в данном случае было бы (2000 2000 2000).
В-третьих, при определённых значениях купюр и размениваемой суммы алгоритм может зайти в тупик и не найти верного решения:
> (define *купюры* '(2000 1500))
> (оптимальный-размен 4500)
(2000 2000)
Возможно, полный рекурсивный перебор?
Следующая мысль, приходящая в голову – реализовать полный перебор методом рекурсивного спуска. Сразу ясно, что это наихудшее по времени и памяти решение, перебирающее и хранящее в качестве промежуточных результатов все возможные комбинации купюр, дающие сумму не выше заданной. Кроме того, обход тупиков в таком случае будет довольно запутанным делом, поэтому не станем тратить силы на программирование этого решения, трудоёмкого в написании и убогого по ожидаемому результату.
Недетерминированное программирование
Подумаем, как нам ограничить ненужные переборы в рекурсии, а заодно справиться с проблемой тупиков. Для этого нужен какой-то механизм отсечки логических ветвей алгоритма, зашедших не туда. Если смотреть в общем, язык Scheme предлагает для решения неудобств с выходом из функции в неактуальное уже место механизм продолжений (continuations). Однако, пользоваться механизмом продолжений в исходном виде по существу не сильно привлекательнее, чем строить программу на голых go to. Поэтому на базе продолжений обычно строятся более приближённые к практическим задачам механизмы, одним из которых является недетерминированная специальная форма amb. Воспользуемся, например, реализацией Такафуми Шидо.
Специальная форма amb принимает произвольное число параметров и имеет следующую денотационную семантику:
(amb)означает выбор из нуля альтернатив, то есть то, что алгоритм зашёл не туда.
(amb x)означает выбор из одной альтернативы, то есть то же самое, что просто x.
(amb x1 x2 ... xN), где N ⩾ 2, означает выбор из N альтернатив. При этом наша программа как бы распадается в мультивселенной на N разных программ, в каждой из которых реализовался свой вариант значения функции amb. Буквально как если бы мы кинули игральный кубик с N значениями, и рассматривали бы разные миры, в каждом из которых на кубике выпало бы своё значение. В дальнейшем (в отличие от квантовых мультивселенных) эти программы можно вновь собрать из разных миров в множество их результатов в одном мире формой set-of.
Заметим, что amb не следует понимать как функцию порождения параллельных потоков выполнения вроде fork() (хотя такие интерпретации операционной семантики amb в истории встречались). Скорее, по обычному механизму реализации это более похоже на сопрограммы (coroutines) – поток выполнения один, но связан с текстом программы нелинейно.
(assert condition) – форма, означающая, что в этом месте программы должно выполняться условие condition (и сама имеющая значение этого условия). Если условие ложно, то мы оказались в неправильном мире, то есть наш алгоритм зашёл в тупик. Ввиду своей семантики, обычно форма assert используется императивно.
(set-of expr) – форма, возвращающая список всех допустимых значений выражения expr в разных мирах.
Реализация amb от Шидо (amb.scm):
Скрытый текст
(define fail #f)
(define-syntax amb
(syntax-rules ()
((_) (fail))
((_ a) a)
((_ a b ...)
(let ((fail0 fail))
(call/cc
(lambda (cc)
(set! fail
(lambda ()
(set! fail fail0)
(cc (amb b ...))))
(cc a)))))))
(define-syntax set-of
(syntax-rules ()
((_ s)
(let ((acc '()))
(amb (let ((v s))
(set! acc (cons v acc))
(fail))
(reverse! acc))))))
(define (assert pred)
(or pred (amb)))
(call/cc
(lambda (cc)
(set! fail
(lambda ()
(cc 'no-choise)))))В нашей программе, по существу, будет использоваться одна недетерминированная конструкция:
(let
((банкнота (amb-list купюры)))
(assert (>= сумма банкнота))
...)которая означает, что мы выбираем любую банкноту из имеющихся у нас купюр и удостоверяемся, что она применима к сумме в нашей ситуации.
Заведём глобальную переменную *минимальная-длина*, которая всегда будет содержать наилучшую на данный момент длину найденного разбиения суммы на банкноты. Тогда, если цепочка рекурсии заведёт нас более чем на столько шагов, сколько содержится в этой переменной – мы точно знаем, что попали не туда. Используем конструкцию
(assert (<= (length аккумулятор) *минимальная-длина*))чтобы отсечь неконкурентоспособные рекурсивные спуски. Именно поэтому нам потребуется рекурсия с аккумулятором, чтобы контролировать длину результата на прямом, а не на обратном ходе рекурсии.
При этом мы неявно будем пользоваться тем фактом, что недетерминированные выборы фактически выполняются слева направо, поэтому первая цепочка выборов в отсортированном по убыванию списке номиналов купюр будет напоминать жадный алгоритм, поэтому у нас будут основания надеяться на быстрое получение хорошего результата для сравнения с ним следующих длин.
Кроме того, здесь перед нами встаёт проблема различения перестановок, таких как, например (5000 1000) и (1000 5000). Если бы мы использовали язык программирования с более развитыми структурами данных, то могли бы построить тип или класс несортированных списков, который решал бы эту проблему в корне. Но так как мы решили использовать Scheme, то просто отсортируем результирующие списки и выкинем дубликаты. Сортировка здесь является незначительной проблемой, так как списки у нас очень короткие, а для длинных списков возникают более существенные обстоятельства.
Код недетерминированной программы на Scheme:
(include "amb.scm")
(define *купюры* '(5000 2000 1000 500 200 100))
(define *минимальная-длина* +inf.0)
(define (amb-list l)
(cond
((null? l) (amb))
(else (amb (car l) (amb-list (cdr l))))))
(define (unique x)
(cond
((null? x) '())
((member (car x) (cdr x)) (unique (cdr x)))
(else (cons (car x) (unique (cdr x))))))
(define (недетерминированный-размен сумма купюры)
(define (шаг-размена сумма аккумулятор купюры)
(assert (<= (length аккумулятор) *минимальная-длина*))
(cond
((zero? сумма) аккумулятор)
(else
(let
((банкнота (amb-list купюры)))
(assert (>= сумма банкнота))
(шаг-размена (- сумма банкнота) (cons банкнота аккумулятор) купюры)))))
(let
((выдача (list-sort >= (шаг-размена сумма '() купюры))))
(when (< (length выдача) *минимальная-длина*)
(set! *минимальная-длина* (length выдача)))
выдача))
(define (оптимальный-размен сумма)
(set! *минимальная-длина* +inf.0)
(let*
((купюры (list-sort >= *купюры*))
(варианты-размена
(unique
(set-of
(недетерминированный-размен сумма купюры))))
(получившийся-минимум (apply min (map length варианты-размена))))
(filter (lambda (вариант)
(= получившийся-минимум (length вариант)))
варианты-размена)))Проверим:
> (оптимальный-размен 14900)
((5000 5000 2000 2000 500 200 200))
> (define *купюры* '(3000 2000 1000))
> (оптимальный-размен 4000)
((2000 2000) (3000 1000))
> (define *купюры* '(3000 2000))
> (оптимальный-размен 4000)
((2000 2000))
Данный алгоритм в точности решает нашу задачу, и с точки зрения денотационной семантики никаких вопросов к нему нет. К сожалению, его операционная семантика такова, что на значительном количестве выданных банкнот и номиналов купюр он работает очень долго, использует огромное количество памяти, и в реальных условиях в банкомате вы его решения не дождётесь. Например, вызов
> (оптимальный-размен 100500)
при стандартном множестве купюр просто завесит вашу машину, и в конце концов, скорее всего, программа вылетит по переполнению виртуальной памяти.
Динамическое программирование
Попробуем применить динамическое программирование. Общий подход здесь состоит в том, чтобы решать задачу "от конца к началу". На первом шаге мы берём список исходных купюр и проверяем, нет ли среди них ответа за один ход. Если есть, задача решена.
Если ответа нет, мы выполняем шаг динамического программирования. Для этого мы строим список всех решений следующего уровня, добавляя каждую из возможных купюр к каждому из возможных решений текущего уровня. Так, например, из всех решений с одной купюрой у нас получаются все решения с двумя купюрами. Мы проверяем, нет ли в построенном списке решений за текущее число ходов. Если таковые нашлись, то это и есть все решения нашей задачи. Если нет, уходим на следующий шаг, строя списки на единицу длиннее.
Для оптимизации на каждом шаге можно сразу исключать решения, дающие сумму больше заданной, так как никаким приписыванием дополнительных купюр из них уже ничего путного не получится.
Для представления шага динамического программирования используем ассоциативный список, в котором значениями элементов являются все возможные комбинации заданного количества купюр, а ключами – суммы данных комбинаций.
Код на Scheme:
(define *купюры* '(5000 2000 1000 500 200 100))
(define (alist l)
(map (lambda (x) (list x x)) l))
(define (unique x)
(cond
((null? x) '())
((member (car x) (cdr x)) (unique (cdr x)))
(else (cons (car x) (unique (cdr x))))))
(define (добавить купюра alist)
(cond
((null? alist) '())
(else (cons (cons (+ (caar alist) купюра)
(list-sort >= (cons купюра (cdar alist))))
(добавить купюра (cdr alist))))))
(define (нарастить сумма общий-список)
(let
((список-уровня (unique
(apply append
(map
(lambda (купюра)
(filter
(lambda (p)
(<= (car p) сумма))
(добавить купюра общий-список)))
*купюры*)))))
(cond
((null? список-уровня) '())
((null? список-уровня) '())
((assq сумма список-уровня) список-уровня)
(else (нарастить сумма список-уровня)))))
(define (оптимальный-размен сумма)
(cond
((member сумма *купюры*) (list сумма))
(else (map cdr (filter
(lambda (p) (= (car p) сумма))
(нарастить сумма (alist *купюры*)))))))Проверим:
> (оптимальный-размен 14900)
((5000 5000 2000 2000 500 200 200))
> (define *купюры* '(3000 2000 1000))
> (оптимальный-размен 4000)
((2000 2000) (3000 1000))
> (define *купюры* '(3000 2000))
> (оптимальный-размен 4000)
((2000 2000))
На стандартном множестве купюр этот алгоритм в среднем работает быстрее предыдущего, но всё равно выдача 100500 рублей труднодостижима.
Тут есть некоторое поле для оптимизации, связанное с тем, что можно хранить промежуточные результаты в хеш-таблице, можно сравнивать поколения между собой и выкидывать более длинные последовательности, имеющие более короткие аналоги. В комментариях @wataruпривёл значительно более эффективный способ динамического программирования, который действует в два этапа и сначала вычисляет ожидаемый размер выборки для каждой суммы, а потом отсекает по этому размеру ветви полного перебора.
Но всё это радикально не решает проблему комбинаторного взрыва при большом количестве купюр в выдаче.
Пробуем думать
Если не получилась сходу общая оптимизация, попробуем подумать над частной.
Можно заметить следующий замечательный факт. Вычислим наименьшее общее кратное (НОК) всех имеющихся номиналов купюр, то есть число, которое может быть выдано купюрами любого одного номинала. Для стандартного набора рублей НОК равно 10000.
Введём понятие "универсальная сумма", определив её как такую сумму, при достижении которой из выдачи можно вычесть НОК, и никакое разбиение остатка от этого не изменится. Мне поначалу казалось, что универсальная сумма - это всегда и есть НОК, но ниже в комментариях @wataru показал, что это не так. Берём для универсальной суммы верхнюю оценку @wataru, которая для стандартного набора рублей универсальная сумма равна 51200. Любую сумму, большую 51200, можно пошагово уменьшать на 10000 рублей путём выдачи двух пятёрок, и дальше уже думать только про остаток. Это даёт нам решение задачи в любом практическом случае, так как сумму в пределах 51200 рублей мы в состоянии разбить за приемлемое время при помощи динамического алгоритма.
Код на Scheme:
(define *купюры* '(5000 2000 1000 500 200 100))
(define (alist l)
(map (lambda (x) (list x x)) l))
(define (unique x)
(cond
((null? x) '())
((member (car x) (cdr x)) (unique (cdr x)))
(else (cons (car x) (unique (cdr x))))))
(define (добавить купюра alist)
(cond
((null? alist) '())
(else (cons (cons (+ (caar alist) купюра)
(list-sort >= (cons купюра (cdar alist))))
(добавить купюра (cdr alist))))))
(define (нарастить сумма общий-список)
(let
((список-уровня (unique
(apply append
(map
(lambda (купюра)
(filter
(lambda (p)
(<= (car p) сумма))
(добавить купюра общий-список)))
*купюры*)))))
(cond
((null? список-уровня) '())
((assq сумма список-уровня) список-уровня)
(else (нарастить сумма список-уровня)))))
(define (крупный-префикс остаток нок универсальная-сумма банкнота)
(cond
((<= остаток универсальная-сумма) '())
(else
(append
(make-list (/ нок банкнота) банкнота)
(крупный-префикс (- остаток нок) нок универсальная-сумма банкнота)))))
(define (оптимальный-размен сумма)
(let*
((купюры (list-sort >= *купюры*))
(нок (apply lcm купюры))
(универсальная-сумма (apply + (map (lambda (x) (- нок x)) купюры)))
(префикс (крупный-префикс сумма нок универсальная-сумма (car купюры)))
(остаток (- сумма (apply + префикс))))
(cond
((member остаток купюры) (append префикс (list остаток)))
(else (map
(lambda (p)
(append префикс
(cdr p)))
(filter
(lambda (p) (= (car p) остаток))
(нарастить остаток (alist купюры))))))))> (оптимальный-размен 100500)
((5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 500))
Задача для реалистичного банкомата решена!
Но...
К сожалению, понятие универсальной суммы мало нам помогает при близких к взаимно-простым номиналах, которые невозможно упростить этим методом.
Так, например, полное решение для номиналов (83 186 408 419 417 421 423 425 427 429 431 477) и суммы 6249 найти в обозримое время не представляется возможным, хотя оно существует в комментариях @wataruи @DanisGBпривели эффективные решения для этого варианта, что, однако, не решает проблему в общем случае. Универсальная сумма в данном случае по нашей оценке равна 1518687044035536789003185055, а НОК – 126557253669628065750265800, что нам не помогает совсем никак.
Отметим также, что вычитание до универсальной суммы, в отличие от описанных выше общих алгоритмов, создаёт проблемы в варианте задачи с ограниченным количеством купюр. Если купюры старшего номинала кончатся посередине интервала выдачи НОК, и старший номинал не кратен второму (как, например, 5000 и 2000), так что вторым номиналом интервал не добить, то дальше алгоритм неприменим, и мы вынуждены будем вернуться к полному перебору из-за того, что у нас будет мешаться пятёрка с неясной применимостью.
Статья в Википедии, посвящённая решению этой задачи в общем виде, подтверждает её экспоненциальную сложность в общем случае. При этом отмечены частные подходы к её решению, включающие, например, использование быстрого преобразования Фурье для априорного выделения перспективных аттракторов в решении при определённых значениях номиналов купюр.
Отметим также
Специально ещё раз подчеркнём, что очень многое в решении этой задачи зависит от выбранных финансистами номиналов купюр. Так, например, ряд номиналов банкнот в СССР включал 3 рубля, что увеличивало НОК до 300 советских рублей (30000 в современных номиналах), а сам ряд купюр состоял из 7 номиналов, в отличие от 6 используемых в банкоматах сейчас. Всё это серьёзно осложнило бы жизнь советских программистов, если бы в СССР были банкоматы. С другой стороны, они могли бы просто не выдавать трёшки.