Изменения

Здесь будет приведен алгоритм, решающий эту задачу за время <tex> O(nL) </tex>, где <tex>L</tex> — максимальная длина кодового слова, <tex>n</tex> — размер алфавита, c помощью сведения задачи к [[Задача_о_рюкзаке | задаче о рюкзаке]].

Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из <tex>5</tex> символов <tex>A=\{A,B,C, C, D\}</tex>, а частоты символов являются степенями двойки: <tex>P=\{1,2,4, 8, 16\}</tex>. Тогда классический код Хаффмана будет выглядеть следующим образом: