Skip to main content

MAKE CHANGE PROBLEM - DYNAMIC PROGRAMMING


  • Greedy may not give optimal solution everytime.

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 :



#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);
}




Labels:

Comments

Post a Comment

Popular Posts

Adaptive Software Development (ASD)

Adaptive Software Development (ASD) :- Adaptive Software Development(ASD) has been proposed by Jim High smith as technique for building complex software and system. ASD focus on human collaboration and team self-organization. Jim High smith defines an ASD "Life Cycle" that consist of three phases  Speculation Collaboration learning  During speculation, the project is initiated and adaptive cycle planning is conducted. Adaptive cycle planning uses project Initiation information,the customer's mission statement ,basic requirements and project constraint to define the set of release cycles that will be required for the project. Collaboration encompasses communication and team-work but it also enphasizes individualism because individual creativity plays an important role in collaborative thinking.It is all above all,a matter of trust. people working together must trust one another to comment without war help without irritation work as hard as ...
Post a Comment
Read more

Kruskal’s Minimum Spanning Tree Algorithm & Programme

PROBLEM :                  Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. To understand Kruskal's algorithm let us consider the following example − Step 1 - Remove all loops and Parallel Edges Remove all loops and parallel edges from the given graph. In case of parallel edges, keep the one which has the least cost associated and ove all others. Step 2 - Arrange all edges in their increasing order of weight The next step is to create a set of edges and weight, and arrange them in an ascending order of weightage (cost). Step 3 - Add the edge which has the least weightage Now we start adding edges to the graph beginning from the one which has the least weight. Th...
Post a Comment
Read more

Dynamic Systems Development Method (DSDM)

Dynamic Systems Development Method(DSDM) :- Dynamic system development method is approach to system development which as the name suggests develops the system dynamically it is a Rapid application development that uses incremental Prototyping. The DSDM philosophy is borrowed from a modified version of " Pareto Principle " Pareto Principle :-  80% of an application can be delivered in 20% of the time it would take to deliver the complete(100%) application. DSDM is an iterative software process in which each iteration follows 80% rule. That is only enough work is required for each increment to start next increment The remaining work can be completed later when more requirements are known or changes have been requested. DSDM life cycle defines 3 different cycles preceded by 2 additional life cycle activities ( FBFDI ) Feasibility Study :-  establishes the basic business requirements and constraint associated with the application to be built. and Identifie...
Post a Comment
Read more