Dynamic Programming Given a set of distinct coins with these

Dynamic Programming. Given a set of distinct coins with these denominations. D = {15, 10, 5}. use a dynamic programming approach to determine the minimum number of coins needed to make up the amount 50. Be sure to include your recurrence relationship along with any initial conditions and your table.

Solution

Dynamic Programming :-

In mathematics, management science, economics, computer science, and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space.Dynamic programming (usually referred to as DP ) is a very powerful technique to solve a particular class of problems. It demands very elegant formulation of the approach and simple thinking and the coding part is very easy.

Solution for given Problem :-

#include<stdio.h>
int sort(int[],int);
int find_coins(int[],int);
int main()
{
int set,coins[100],i;
printf(\"Enter number of sets of the set :-\\t\");
scanf(\"%d\",&set);
printf(\"Enter the number of coins in each set :\ \");
for(i=0;i<set;i++)
{
scanf(\"%d\",&coins[i]);
}
sort(coins,set);
return 0;
}
int sort(int coins[],int set)
{
int temp,i,j;
for(i=0;i<set;i++)
{
for(j=0;j<set-i;j++)
{
if(coins[j]>coins[j+1])
{
temp=coins[j];
coins[j]=coins[j+1];
coins[j+1]=temp;
}
}
}
find_coins(coins,set);
return 0;
}
int find_coins(int coins[],int set)
{
int i,sum=0,sum1,temp,j,x=-1,y,z;
while(sum<=50)
{
sum=sum+coins[set-1];
sum1=sum-coins[set-1];
x++;
}
for(i=0;i<set-1;i++)
{
if(sum1+coins[i]==50)
{
y=x+1;
z=coins[i];
}
}
printf(\"The minimum number of coins to make up 50 is = %d\ \",y);
printf(\"%d --> %d coins\ \",x,coins[set-1]);
printf(\"1 --> %d coins\",z);
return 0;

}

Sample Output :-

Enter number of sets :- 3
Enter the number of coins in each set :
15
10
5
The minimum number of coins set to make up 50 coins are = 4
3 --> 15 coins set
1 --> 5 coins set