Код Хаффмана с длиной кодового слова не более L бит — различия между версиями
| Строка 2: | Строка 2: | ||
== Задача о банкомате. == | == Задача о банкомате. == | ||
| − | В вариации задаче о банкомате, которую мы рассмотрим, у вас имеется <tex>N</tex> монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы являются степенями двойки и не превышают <tex>2^0</tex>. Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен S (натуральное число), а суммарный вес минимален. | + | В вариации задаче о банкомате, которую мы рассмотрим, у вас имеется <tex>N</tex> монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы являются степенями двойки и не превышают <tex>2^0</tex>. Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен <tex>S</tex> (натуральное число), а суммарный вес минимален. |
Версия 13:24, 17 декабря 2014
Код Хаффмана с длиной слова не более L бит - это вариация классического кода Хоффмана с дополнительным ограничением: длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время , где - максимальная длина кодового слова, - размер алфавита, c помощью сведения задачи к одной из вариаций задачи о банкомате.
Задача о банкомате.
В вариации задаче о банкомате, которую мы рассмотрим, у вас имеется монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы являются степенями двойки и не превышают . Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен (натуральное число), а суммарный вес минимален.
