Изменения
Нет описания правки
При этом <tex>h_{i}</tex> — это длина кодового слова для <tex>i</tex>-го символа.Зная длины кодовых слов, легко восстановить и сам код.
Из последнего утверждения и шага 2 легко заметить, что длина кодового слова, сгенерированного приведенным алгоритмом, действительно не превысит <tex>L</tex>. Оптимальность же кода следует из оптимальности решения задачи о рюкзаке. Действительно, частота символа - это вес предеметов, соответствующих ему. Значит, чем чаще символ встречается в тексте, тем реже он будет попадать в наш рюкзак (будет выгоднее брать предметы аналогичной ценности, но меньшего веса, соответствующие более редким символам), а значит, его код будет короче.
== Восстановление ответа. ==
