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