• Combinational Search and Dynamic Programming
  • Combinational Search and Optimization I
  • Combinational Search and Optimization II
  • Dynamic Programming
• Problems
  • Coin changing problem - Total ways
  • Coin changing problem - Minimum ways

dynamic programming

In mathematics, computer science, economics, and bioinformatics, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure (described below). When applicable, the method takes far less time than naive methods that don’t take advantage of the subproblem overlap (like depth-first search).

Read more

Combinational Search and Dynamic Programming

Recently, I came across these three videos about the Combinational Search and Dynamic Programming and I think these videos explains the complexity in great simplicity. I highly recommend for one who is beginner and want to learn the fundamentals.

Combinational Search and Optimization I

Combinational Search and Optimization II

Dynamic Programming

Problems

Coin changing problem - Total ways

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

The first step is to come up with the simple recursive solution which solves this problem. Once that done we can map that problem to the dynamic problem(DP) solution.

For DP solution there are two ways top-down (with recursive called memoization technique) or bottom up (with iteration).

This article explains about above quote in detail.

The recursive solution of this problem would look like this. If one have watched above videos, you would understand the logic or it is explained here. Till now, it is all same like any other source or web pages across internet for solution of this problem. But, soon it’s going to differ.

 
 // Returns the count of ways we can sum  S[0...m-1] coins to get sum n
 int count( int S[], int m, int n )
 {
     // If n is 0 then there is 1 solution (do not include any coin)
     if (n == 0)
     return 1;
 
     // If n is less than 0 then no solution exists
    if (n < 0)
    return 0;

    // If there are no coins and n is greater than 0, then no solution exist
    if (m <=0 && n >= 1)
    return 0;

    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

Cracking the coding interview book also have same problem with below recursive solution. In this code S = {25, 10, 5, 1}

 
 int getchange(int n, int denom)
 {
     int next_denom = 0;
 
     switch(denom) {
     case 25:
         next_denom = 10;
         break;

    case 10:
        next_denom = 5;
        break;

    case 5:
        next_denom = 1;
        break;

    case 1:
        return 1;
    }

    int ways = 0;

    for (int i = 0; i*denom <= n; i++) {
    ways += getchange(n - i*denom, next_denom);
    }

    return ways;
}

As explained in dynamic programming video above, lets convert this program into dynamic programming program. This is a top down approach.

 
 
 define N 50
 define CHANGESIZE 4
 
 int changeSize;
 
 // Sum upto 50
 int table[N + 1][CHANGESIZE + 1];

// Converted top down DP version of count()
int countDP(int S[], int m, int n)
{
    if (n == 0) {
    table[n][m] = 1;
    return table[n][m];
    }
    if (n < 0) {
    return 0;
    }

    if (m <=0 && n >= 1)
    return 0;

    if (n-S[m-1] < 0) {
    return 0;
    }

    if (table[n][m-1] == 0) {
    table[n][m-1] = countDP(S, m-1, n);
    }

    if (table[n-S[m-1]][m] == 0) {
    table[n-S[m-1]][m] = countDP(S, m, n-S[m-1]);
    }

    return (table[n][m-1] + table[n-S[m-1]][m]);
}

void inittable()
{
    for (int i = 0; i < N + 1 ; i++) {
    for (int j = 0; j < changeSize + 1; j++) {
        table[i][j] = 0;
    }
    }

    return;
}

int main()
{
    int ways = 0;
    int change[4] = {25, 10, 5, 1};
    changeSize = sizeof(change)/sizeof(change[0]);

    for (int sum = 1; sum < 50; sum++) {
    printf("Sum %d\n", sum);        
    ways = countDP(change, changeSize, sum);
    printf("CountDP = %d\n", ways);
    printf("============\n\n");

    inittable();
    }

    return 0;
}

Coin changing problem - Minimum ways

Given a list of N coins, their values (V1, V2, … , VN), 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.

This problem has been published at various sites including following with explanation in great detail

• Topcoder coin changing problem
• Dynamic programming

Topcode article explains the bottom up part very well. The idea here is to determine how many minimum coins are required for sum 1 then for sum 2 then for sum 3 and so on.

TopCoder article says

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-V1= 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.

I followed this explanation and tried to come up with the program which is as follows

 
 //  Given a list of N coins, their values (V1, V2, ... , VN),
 //  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.
 
 #include <stdio.h>
 
 int mincount(int change[], int changeSize, int SUM)
{
    int table[SUM + 1];

    table[0] = 0;
    int min = INT32_MAX;


    for (int sum = 1; sum <= SUM; sum++) {
    for (int j = 0; j < changeSize; j++) {
        // Pick first coin and substract with the sum
        // Check if sum is less than 0
        if (sum - change[j] < 0) {
        continue;
        } else if (sum - change[j] == 0) {
        // This is the case when sum is either 1, 5, 10, 25
        // In this case mininum number of coin required is 1
        min = 1;
        break;
        }

        // This is case when we say sum is 3
        // In this case lets start with first coint which is 1
        // If we choose coint 1 then the sum left os 3 - 1 = 2
        // Given we are calculating for sum 3 means we have already
        // calculated for sum 2. So go to table for sum = 2 and
        // get the min number of ways sum 2 is computed.
        // Here i is the sum i.e. lets say as per our example
        // i = 3, j = 0
        // 1 + table[3 - change[0]];
        // 1 + table[3 - 1];
        // 1 + table[2];
        // 1 + 2 = 3
        // Sum 3 requires at least 3 coins {1, 1, 1}

        if (min > (1 + table[sum - change[j]])) {
        min = 1 + table[sum - change[j]];
        }
    }
    table[sum] = min;
    min = INT32_MAX;
    }

    for (int i = 0; i <= SUM; i++) {
    printf("SUM[%d]: %d\n", i, table[i]);
    }

    return table[SUM];
}


int main(int argc, const char * argv[])
{
    int change[4] = {1, 5, 10, 25};
    int changeSize = sizeof(change)/sizeof(change[0]);
    int SUM = 16;

    printf("MinChange for sum %d = %d\n", SUM, mincount(change, changeSize, SUM));

    return 0;
}