Изменения

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