Here is a not so elegant solution:
Note that this gives only the cheapest solutions and not the three cheapest solutions!
the question was not to use DP. See Kevins opening post, where you can see that the exercise goes far beyond finding the cheapest solution. For instance, a big role is the quality of the solution. Then there is finding the three cheapest solutions instead of only the cheapest. The DP is not mentioned, it was a suggestion of mine. Another way would be to see this exercise as the famous coin problem, where we have in this case 4 coins of value 1,2, 3 and 4, and finding all the ways to write N as the sum of a combination of these values. Then giving a suitable cost-function to these combinations, and findig the cheapest ones.