82
правки
Изменения
Нет описания правки
# Отсортируем символы алфавита в порядке возрастания их частот.
# Для каждого символа создадим <tex>L</tex> предметов ценностью <tex>2^{-1}..2^{-L}</tex>, каждый из которых имеет вес <tex>p_{i}</tex>.
# С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью <ex>n - 1</tex> (<tex>n</tex> — размер алфавита) с минимальным суммарным весом.
# Посчитаем массив <tex>H=\{h_{1},h_{2},...,h_{n}\}</tex>, где <tex>h_{i}</tex> — количество предметов ценностью <tex>p_{i}</tex>, которые попали в наш набор.
