Suppose I have 4 coins of denominations 1 3 4 5. I want to make it 7. I learn how to find how many possible ways that can be done. But I want to determine what is the minimum number of coins that must be used to do that. Example: 5+1+1=7 again 3+4=7. So the minimum number of coins is 2. Any pseudo code or explanation or source code will be helpful
If you want to make change for the number n, set up an array number_of_coins[n] and fill it in from left to right. number_of_coins[0] is 0, obviously. The next few you can do by hand (although once you have an algorithm it will fill them in automatically). To fill in larger entries m in the array, think about this: what if I removed 1 cent from m? Or 3 cents? Or 4 cents? Or 5 cents?
Once you have the number of coins array up to n, you can walk backwards through it to find the exact coins to use.