dynamic programming

Solving a payment without change problem

I have come across an interesting problem. A customer is standing at the checkout of a grocery store with his purchases and is asked to pay the exact amount without creating any change. There are notes of various denominations in his pockets in random order (note denomination is not tied to a real bank notes, the only boundary is that it is an integer greater than 0). The objective is to pick up the necessary sum or indicate that it is not possible. If several solutions are possible then any of them is acceptable. So, let’s solve it using C# language.