An Example of Dynamic Programming: Coin Exchange

Problem:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Solution Technique:
Dynamic Programming.


Solution Detail:

• Lets say you have a set of N coins. Consider an array. The name of the array is coins. It holds  the values of all the coins.       
  

          coins[0] = 0;    means no coins or a coin which has zero value.
                    coins[1] = 3;    means the first coin has a value of 3.
                    ....
                    ...
                    .
                    coins[N] = 71;  means the Nth coin has a value of 71.

• T is Target Value

• VN is Value of the Nth coin. If coins[1] = 3, it means V1 = 3.

• Let us consider another array. The name of the array is count. It is a two dimensional array. Each entry count[i][j] of this array means In how many ways you can make up j,  using the set of coins found from coins[0.....i]. Where 0 <= i <= N and 0 <= j <= T

• So, if your target is T and you have N coins of different values then the solution is coins[N][T]

• If T=0, then there is always one way to make up the target value with whatever coin you have. That means 

coins[0][0]=1;

coins[1][0]=1;

coins[2][0]=1;

.....

...

. 

coins[T][0]=1;

• And if T > 0 and you have no coins or only one kind of coin of zero value, then there is no way to make up the target value. That means

coins[0][1]=0;

coins[0][2]=0;

coins[0][3]=0;

.....

...

. 

coins[0][T]=0;  

• Now, how to calculate coins[i][j] where both i and j is greater than 0 ? To answer the question, divide the problem into three parts. 

           1. One set of solutions which doesn't contain the ith coin

           2. Another set of solution which contain the ith coin at least once

           3. Another(only one) solution that contains only the ith coin, nothing else
     

• Notice that, the second set may already have the solution that is mentioned  in the third set. That means the second and third set is not disjoint. This problem has been taken care of at the below yellow marked text.

• At First, check, in how many ways you can make up j  without using the ith element. This refer to the array entry coins[i-1][j].

• After that check, in how many ways you can make up j-Vi using the ith coin along with the all other i-1 coins. This refer to the array entry coins[i][j-Vi]. This is because, if you can make up j-Vi then you can also make up j just by adding one more ith coin. In this set of solutions there will be at least one ith coin as you are adding it explicitly. It may be the case that j-Vi < 0. In that case consider  coins[i][j-Vi] = 0.

• At last, If Vi divides j,it means there is one more solution to make up J. In that solution you use j/Vi number of ith coins and no coins of other values than Vi. Anyway, we do not consider this solution in our count if Vi divides j-Vi also.

• So, from the above three points we can write:

Count[i][j] = Count[i-1][j] + Count[i][j-Vi] (if j-Vi >=0) 

+ 1 (if Vi divides j and Vi doesnt divide j-Vi)

• If T is the final target value and you have N coins then the solution is: coins[N][T] 

Example Table:

Target Amount         ->    |0    1    2    3    4    5    6

 ----------------------------------------------------------------------------------

 V0 = coins[0] = 0       ->    |1    0    0    0    0    0    0  

 V1 = coins[1] = 1       ->    |1    1    1    1    1    1    1  

 V2 = coins[2] = 2       ->    |1    1    2    2    3    3    4  

 V3 = coins[3] = 5       ->    |1    1    2    2    3    4    5  

 V4 = coins[4] = 10     ->    |1    1    2    2    3    4    5  

 V5 = coins[5] = 20     ->    |1    1    2    2    3    4    5  

 V6 = coins[6] = 50     ->    |1    1    2    2    3    4    5  

 V7 = coins[7] = 100   ->    |1    1    2    2    3    4    5  

V8 = coins[8] = 200  ->    |1    1    2    2    3    4    5

C Code:

#include<stdio.h>


/* The Problem Starts
In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
    1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
    1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
 The problem Ends */


int main()
{

int i,j,destination;

int coins[9]={0,1,2,5,10,20,50,100,200};

printf("Please enter a destination amount:(>=0):");
scanf("%d",&destination);
  
int count[9][destination+1];

count[0][0]=1;
for(i=0;i<=8;i++)
    count[i][0]=1;
for(i=1;i<=destination;i++)
    count[0][i]=0;

int x=0;
    for(i=1;i<=8;i++)
    {
        for(j=1;j<=destination;j++)
        {
            count[i][j]=0;
            if((j-coins[i])>=0)
            {
             count[i][j] = count[i][j]+count[i][j-coins[i]]+count[i-1][j];
                  
            }
            if((j-coins[i]) < 0)
            {
                count[i][j] = count[i][j]+count[i-1][j];
            }
            if((j%coins[i])==0)
            {
                if( (j-coins[i])%coins[i]!=0)
                count[i][j]++;
            }      
        }
    }
printf("\n*********The final count is:%d\n",count[8][destination]);

      
    if(destination<=15)
    {
        printf("\nThe whole two dimensional table is:\n\n");
        for(i=0;i<=8;i++)
        {
            if(i==0)
            {
                printf("    Amt->    |");
                for(j=0;j<=destination;j++)
                printf("%d    ",j);
              
                printf("\n           ");
                for(j=0;j<=destination;j++)
                printf("_    ",j);
            printf("\n\n");
            }

        printf("coins[%d] %d    |",i,coins[i]);
            for(j=0;j<=destination;j++)
                {printf("%d    ",count[i][j]);}
        printf("\n");
        }
    }

printf("\n**NB:All calculations are done using int data type. Overflow is very easy.\n\nn");

return 0;
}