A coin collector has

- four €$1/2$ coins of numismatic values $4$, $8$, $13$ and $15$ respectively,
- three €$1/4$ coins of numismatic values $3$, $5$ and $6$ respectively,
- five €$1/8$ coins of numismatic values $2$, $2$, $4$, $6$ and $11$ respectively,

First, €$1/8$ coins are grouped two by two to form two packages of €$1/4$ with respective numismatic values $4$ and $10$, dropping the coin of numismatic value $11$.

Then, these two packages are merged with the €$1/4$ coins and sorted. Coins and packages of €$1/4$ are grouped, which produces two €$1/2$ packages of respective numismatic values $7$ and $11$, disregarding the package of numismatic value $10$.

Going on, these two packages are merged with the €$1/2$ coins and sorted. Finally, coins and packages of €$1/2$ are processed, which gives three packages of respective numismatic values $11$, $19$ and $28$. The picture illustrates the whole process.

The first two packages give the solution: $2$ euros composed of two €$1/8$ coins of numismatic values $2$ each; three €$1/4$ coins of numismatic values $3$, $5$ and $6$; and two €$1/2$ coins of numismatic values $4$ and $8$ for a total numismatic value of $30$.

Given the frequencies of alphabet letters, the Huffman algorithm builds an optimal prefix code to encode the letters in such a way that encodings are as short as possible. In the general case there is no constraint on the length of the codewords. But sometimes one may want to bound the codeword length. Building a code satisfying such a constraint is the subject of this problem.

The coin collector's problem is an example of where the constraint is used. Collectors have coins with two independent properties: denominations (currency values) and numismatic values (collector values). Their goal is to collect a sum $N$ while minimising the total numismatic value.

Let denominations be integer powers of $2$: $2^{-i}$ with $1\leq i \leq L$. Coins are organised as follows: there is a list for each denomination in which coins are sorted in increasing order of their numismatic values.

The method consists in grouping adjacent coins two by two in the list of smaller denominations, dropping the last coin if their number is odd. The numismatic value of a package is the sum of numismatic values of the two coins. Newly formed packages are associated with the coins of the next smallest denomination (sorted in increasing numismatic value). The process is repeated until the list of coins of denomination $2^{-1}$ is processed.

Design an algorithm that computes for a list of $n$ frequencies an optimal
length-limited Huffman code in which no codeword is longer than $L$ and that
runs in time $O(nL)$.

Reduce the problem to the binary coin collector's problem.

Algorithm PackageMerge$(S,L)$ implements the strategy described in the example for a set $S$ of coins with denominations between $2^{-L}$ and $2^{-1}$. Package$(S)$ groups two by two consecutive items of $S$ and Merge$(S,P)$ merges two sorted lists.

Eventually, the first $N$ items of the list PackageMerge$(S,L)$ have the lowest numismatic values and are selected to form the solution.

PackageMerge$(S \textrm{ set of coins}, L)$

\begin{algorithmic} \FOR{$d\leftarrow 1$ \TO $L$} \STATE $S_d\leftarrow \mbox{list of coins of $S$ with denomination $2^{-}$ $^d$}$ \STATE $\qquad$ sorted by increasing numismatic value \ENDFOR \FOR{$d\leftarrow L$ \DOWNTO $1$} \STATE $P\leftarrow$ Package$(S_d)$ \STATE $S_{d-1}\leftarrow$ Merge$(S_{d-1},P)$ \ENDFOR \RETURN{$S_0$} \end{algorithmic}

Both Package$(S')$ and Merge$(S',P')$ run in linear time according to $n=|S|$. Thus, provided that the lists of coins are already sorted, the algorithm PackageMerge$(S,L)$ runs in time and space $O(nL)$.