The problem can be solved using a simple greedy algorithm. We first sort the jewellery pieces by value. Then, for each piece of jewellery starting with the most valuable, we do the following:

• we choose the bag with the smallest maximum mass out of bags that are able to store the current piece of jewellery, if there is such a bag available; we remove that bag from the set of available bags and add the value of the current jewellery piece to the solution
• if there is no available bag that can store the current piece, we skip the piece and continue

In order to implement the above algorithm, we need a data structure efficiently supporting the following three operations: insert a number, find the first number larger than some number ~x~ (or report there is no such number), remove a number. If using C++, a standard STL structure – multiset – can be used for this purpose.

Pascal programmers will need some more effort to solve this problem. For them, we recommend the following algorithm, with a very similar basic idea as the algorithm above.

While the above algorithm requires coding a balanced binary tree or a Fenwick tree, the following algorithm requires only sorting and the binary heap, which are somewhat simpler to implement.

The binary heap is a data structure supporting three operations: insert a number, find the maximum number, remove the maximum number. It is one possible implementation of a priority queue (for example, in C++ STL).

The algorithm is as follows:

• sort the jewellery and bags together in a single array by mass/capacity
• iterate over the sorted array starting with the minimum mass/capacity
• if the current item is a jewellery piece, insert its value into the heap
• if the current item is a bag and if the heap is not empty, take the most valuable piece of jewellery so far (which is guaranteed to fit into the current bag because of the sorting), remove it from the heap and add its value to the solution

The proof that the above two algorithms are correct is left as an exercise for the reader.