Код Хаффмана с длиной кодового слова не более L бит

Код Хаффмана с длиной слова не более L бит - это вариация классического кода Хоффмана с дополнительным ограничением: длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время [math] O(nL) [/math], где [math]L[/math] - максимальная длина кодового слова, [math]n[/math] - размер алфавита, c помощью сведения задачи к одной из вариаций задачи о банкомате.

Задача о банкомате.

В вариации задаче о банкомате, которую мы рассмотрим, у вас имеется [math]N[/math] монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы являются степенями двойки и не превышают [math]2^0[/math]. Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен [math]S[/math] (натуральное число), а суммарный вес минимален.

Алгоритм решения задачи о банкомате.

Рассмотрим алгоритм решения приведенной выше вариации задачи о банкомате.

1. Разделим имеющиеся у нас монеты на списки по номиналу (свой список для каждого номинала) и упорядочим монеты по возрастанию весов внутри списков.