A road named NoNameUno

In DP 2, we saw that simple one dimensional problem could be fairly easy to get the DP functional equation, without going thru the recurrence relations first. This is because functional equation does not have too much dependencies. An example is Fibonacci number.

 Here we talk about CoinChange problem which is somewhat difficult to comeup with DP functional equation right away. So it is best to get a recurrence relation and solve it first. A correct solution at first is always a good idea ! Then analyze the execution and perhaps come up with DP functional equation.

I'M NO EXPERT in DP analysis, so one step at a time.

Problem statement:

Given a set of coins with infinite supplies of each denominations, like: S = {1, 5, 10, 25 }. So the set consist of pennies, nickels, dimes, and quaters.

Question: What is the minimal number of coins that make up to an amount of changes, say N.

Ex: N = 11 => {1, 10} or { 1, 5, 5}. MinNoOfCoins = 2.

Caution: Try to follow the DP 2 methods to come up with DP functional equations straight out and see if this could be easy or complex. 

Note that DP problems solving in most cases is to look at substructure from backtracking point of view.

So the recursive definition is -

MinNoOfCoins(N ) = min { 1+MinNoOfCoins(N-1); 1+MinNoOfCoins(N-5); 1+ MinNoOfCoins(N-10); 1+MinNoOfCoins(N-25)}, depending on what is the last denomination being picked.

 For this recursive definition, here is the implementation ---

//

//  Created by Admin on 5/6/18.

//  Copyright © 2018 AdminProkash Sinha. All rights reserved.

//

#include <stdio.h>

/*

 * Given a set of coins S = { 1, 5, 10, 25 } pennies, nickels, dimes, quaters

 * Given N the change Amout, say 73 or 62 or 49 ...

 * Find the min number of coins whose sum is N

 *

 * -- A straight DP functional equation may not be simple thing to do, becasue

 * -- D(N ) defined as Minmum no. of coins to get changes to N, then

 * -- D(N) = D(N-1) + D(N-5) + D(N-10) + D(N-25)

 * --- priming the table would be hard, laborious, and confusing.

 * -- So lets try the normal steps -- Find a recurrence equation.

 ---

 Let's MinCoins(N) = min of {  1+ Minconins(N-1); 1+ Mincoins(N-5); 1 + Mincoins(N-10); +1 + Mincoins(N-25)  }

 */

int Mincoins( int arr[], int Nodenomination, int N)

{

    int mincoins = N ;  /* the worst we can do using pennies */

    if ( N <= 0) return 0;

    /* array of coins from the denomination set S = { 1, 5, 10, 25} for example */

    for (int i = 0; i < Nodenomination; i ++) {

        if (N == arr[i])

            return 1;    /* just one more coin needed */

    }

    for (int i = 0; i < Nodenomination; i ++) {

        int numcoins;

        if ( arr[i] < N) {

            numcoins = 1 + Mincoins(arr, Nodenomination, N - arr[i]);

            mincoins = ( mincoins < numcoins) ? mincoins : numcoins;

        }

    }

    return mincoins;

}

int main(int argc, const char * argv[]) {

    int coins_set[] = { 1, 5, 10, 25};

    int MinNoOfCoins;

    int Nodenomination = sizeof(coins_set)/ sizeof(coins_set[0]);

    MinNoOfCoins = Mincoins(coins_set, Nodenomination,  62 /*49*/);

    // insert code here...

    printf("MinNoOfCoins = %d\n", MinNoOfCoins);

    return 0;

}

RK: If we try to find the minimum numbers of coins for a change of 4093 cents, the above implementation could take some time.