We need some way to narrow down the subsets of N that we consider. Perhaps we could start by enumerating the subsets of N lexicographically, and then performing a binary search on the array of subsets to help us choose? Just a thought, not very developed yet.

I just started working on this problem, but here is a rough outline:

1. Generate all subsets of N coins.

2. For each subset, generate the minimum multi-set required to materialize the total values 1...M; say for subset of coins N(i), we name each multi-set of coins N(i),M(j) where j is some value between 1 and M.

3. For fixed i, get the average over j for each multi-set N(i),M(j).

4. Choose the subset N(i) that maps to the lowest average size of the multi-sets that are generated from N(i).

Time will be O(2^N), since we are generating each subset of N. Feedback much encouraged to get this down to a polynomial solution.