monetization problem
Problem:
consider that you have rs 1000,500,100,50,10,5,2,1 rupee notes.Given an amount of money you have to find the possible combination of rupee notes of best possible solution (i.e combination with least no.of.notes)
Example : 450 rs
The solution is (100+100+100+100+50) and not (100+100+50+50+50+50+50) or (50+50+50+50+50+50+50+50)
This problem is a classic example of greedy method.
Program:
#include<stdio.h>
int main()
{
int amount=0,i,count=0;
int money[9]={1000,500,100,50,20,10,5,2,1};
printf("Enter the amount \n");
scanf("%d",&amount);
for(i=0;i<9;i++)
{
if(amount>=money[i])
{
int times=amount/money[i];
count=count+times;
for(int j=0;j<times;j++)
{
printf("%d ",money[i]);
}
amount=amount%money[i];
}
}
printf("\n %d notes are needeed.",count);
return 0;
}
output:
Enter the amount
987
500 100 100 100 100 50 20 10 5 2
10 notes are needeed.
Comments
Post a Comment