The minimum number of coins the sum of which is S

The precise answer to this problem is well explained here. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

This is a classic Knapsack problem, take a look here for some more information: Wikipedia Knapsack Problem

You should also look at some sorting, specifically sorting from Largest to Smallest values.