Код Хаффмана с длиной кодового слова не более L бит
Версия от 13:24, 17 декабря 2014; Ruslan.tkhakokhov (обсуждение | вклад)
Код Хаффмана с длиной слова не более L бит - это вариация классического кода Хоффмана с дополнительным ограничением: длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время
, где - максимальная длина кодового слова, - размер алфавита, c помощью сведения задачи к одной из вариаций задачи о банкомате.Задача о банкомате.
В вариации задаче о банкомате, которую мы рассмотрим, у вас имеется
монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы являются степенями двойки и не превышают . Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен S (натуральное число), а суммарный вес минимален.