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

Popular posts from this blog

c++ program to print string along the diagonals of the matrix.

Kollywood Game

C program to print the following Pattern