Minimum number of coins to get particular amount, given multiple denomination

Question: You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount OR S), find the minimum number of coins required to get the exact amount.

Problem statement

"Given a list of N coins, their values (V₁, V₂, ... , V_N), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S."

Examples
Given coins with values 1, 3, and 5.  And the sum S is 11.
Output: 3, 2 coins of 3 and 1 coin of 5
This questions was asked in Amazon written test.

Solution:
We will solve this problem using dynamic programming.
Dynamic programming is a top-down approach: split the larger problem into smaller ones, solve the smaller ones (putting away the solution for each smaller problem somewhere so that it can be used again in case needed later), and combine to produce the solution to the larger problem.

First of all we need to find a state for which an optimal solution is found and with the help of which we can find the optimal solution for the next state.

We will create an array Min[i] for minimal sets with sum = i. Min[0]=0.
We come through i=1 to S inclusive and check whether Min[i]>Min[Min[i-v]+1] for each v in a given array. If so, we set Min[i] to this value.

It is simple - for each coin j, V_j≤i, look at the minimum number of coins found for the i-V_jsum (we have already found it previously). Let this number be m. If m+1 is less than the minimum number of coins already found for current sum i, then we write the new result for it.

For a better understanding let's take this example:

Given coins with values 1, 3, and 5.And the sum S is set to be 11.

First of all we mark that for state 0 (sum 0) we have found a solution with a minimum number of 0 coins. We then go to sum 1. First, we mark that we haven't yet found a solution for this one (a value of Infinity would be fine). Then we see that only coin 1 is less than or equal to the current sum. Analyzing it, we see that for sum 1-V₁= 0 we have a solution with 0 coins. Because we add one coin to this solution, we'll have a solution with 1 coin for sum 1. It's the only solution yet found for this sum. We write (save) it. Then we proceed to the next state - sum 2. We again see that the only coin which is less or equal to this sum is the first coin, having a value of 1. The optimal solution found for sum (2-1) = 1 is coin 1. This coin 1 plus the first coin will sum up to 2, and thus make a sum of 2 with the help of only 2 coins.This is the best and only solution for sum 2. Now we proceed to sum 3. We now have 2 coins which are to be analyzed - first and second one, having values of 1 and 3. Let's see the first one. There exists a solution for sum 2 (3 - 1) and therefore we can construct from it a solution for sum 3 by adding the first coin to it. Because the best solution for sum 2 that we found has 2 coins, the new solution for sum 3 will have 3 coins. Now let's take the second coin with value equal to 3. The sum for which this coin needs to be added to make 3 , is 0. We know that sum 0 is made up of 0 coins. Thus we can make a sum of 3 with only one coin - 3. We see that it's better than the previous found solution for sum 3 , which was composed of 3 coins. We update it and mark it as having only 1 coin. The same we do for sum 4, and get a solution of 2 coins - 1+3. And so on.

Pseudocode:

Set min[i] = infinity for all i
min[0] = 0

for (i=1 to S)
for (j=0 to N-1)
    if(Vj ≤ i AND Min[i-Vj] < Min[[i])
        THEN Min[i] = Min[i-Vj]+1

Output Min[S]

Here are the solutions found for all sums:

Sum		Min. nr. of coins	Coin value added to a smaller sum to obtain this sum (it is displayed in brackets)
0		0	-
1		1	1 (0)
2		2	1 (1)
3		1	3 (0)
4		2	1 (3)
5		1	5 (0)
6		2	3 (3)
7		3	1 (6)
8		2	3 (5)
9		3	1 (8)
10		2	5 (5)
11		3	1 (10)

As a result we have found a solution of 3 coins which sum up to 11.

Additionally, by tracking data about how we got to a certain sum from a previous one, we can find what coins were used in building it. For example: to sum 11 we got by adding the coin with value 1 to a sum of 10. To sum 10 we got from 5. To sum 5 we got from 0. Thus, we find the coins used are: 1, 5 and 5.