MAKE CHANGE PROBLEM - DYNAMIC PROGRAMMING

• Greedy may not give optimal solution everytime.

Make change Problem - Greedy Algo

Example :

Coins  : { 1 ,  3 , 4  }

Amount : 6

Solution Given By Greedy : { 4 , 1 , 1 }

Optimal Solution : { 3 , 3 }

• Dynamic Programming :

Algo :

fun makechange(N)

{

array d[1...n]=[1,4,6];

array c[1...n,0...N]

for i=1 to n do c[i,0]=0

for j=1 to N do

c[i,j] = if i=1 & j<d[i] then + ∞

else if i=1 then 1+c[1,j-d[1]];

else if j<d[i] then c[i-1,j]

else

min(c[i-1][j] ,1+c[i,j-d[i]]);

return c[n,N];

}

Programme :

Download Programme

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int min(int x,int y)
{
int min;
if(x>y)
{
min=y;
}
else
{
min=x;
}
return min;
}
void make_change(int N)
{
int i,j;
int d[4]={0,1,4,6};
int c[4][N+1];
printf("     ");
for(i=0;i<=N;i++)
{
printf("%d  ",i);
}
printf("\n");
for(i=0;i<4;i++)
{
c[i][0]=0;
printf("%d : ",d[i]);
for(j=0;j<=N;j++)
{
    if(i==0){
    c[0][j]=0;
    printf(" %d ",c[i][j]);
    continue;
    }
if(i==1 && j<d[i])// AMOUNT THAT WE WANT TO MAKE IS LESS THAN THE FIRST AVAILABLE COIN
{
c[i][j]=0;//INDICATES THAT WE CAN'T MAKE MAKE j MONEY USING ith COIN
}
else if(i==1)
{
c[i][j]=1+c[1][j-d[1]];//FOR THE FIRST ROW ONLY BCZ FOR THAT WE CAN NOT ABLE TO FIND min(c[i-1][j],1+c[i][j-d[i]]);
//AND j-d[0] >0 BCZ IT HAS ALREADY CHECKED IN THE FIRST IF CONDITION
}
else if(j<d[i])
{
c[i][j]=c[i-1][j];
}
else
{
c[i][j]=min(c[i-1][j],1+c[i][j-d[i]]);
}
printf(" %d ",c[i][j]);
}
printf("\n");
}
i=3;
j=N;
printf("\nCOINS : ");
while( i>0 && j>0)
    {
        if(c[i][j]==c[i-1][j])
        {
            i--;
        }
        else
        {
            printf("%d ",d[i]);
            j=j-d[i];
        }

    }

}
main()
{
int n;
printf("ENTER AMOUNT WHICH YOU TO MAKE : ");
scanf("%d",&n);
make_change(n);
}