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

Popular posts from this blog

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

-
#include <iostream>
#include<string.h>
using namespace std;

int main()
{
    char name[100];
    cin>>name;
    int i,j;
    for(i=0;i<strlen(name);i++)
    {
        for(j=0;j<strlen(name);j++)
        {
            if(i==j)
            {
                cout<<name[i];
            }
            else if(i+j==strlen(name)-1)
            {
                cout<<name[j];
            }
            else
            {
                cout<<" ";
            }
        }
        cout<<"\n";
    }
    return 0;
}


Note: This works well for only strings with odd number of characters.
EXAMPLE:
input : GLOBE output: G       E    L  B      O    L   B G         E

input :HannahBaker output:
H         r  a       e    n     k      n   a        a B          h          a B        n   a      n     k    a       e  H         r

Read more

C program to print the following Pattern

-
Output: 3                                                                                                                                               33333                                                                                                                                           32223                                                                                                                                           32123                                                                                                                                           32223                                                                                                                                           33333  

5                                                                                                                                                 555555555�����������������������������������������������������������������������������������������������������������…
Read more

Kollywood Game

-
A simple game which we have all played once in their life,Actually according to the program the user has to give the movie name and then he has to find it which sounds silly. i could not come up with any better solution for this , so if you have any better solution please do comment . works better with two players .one has to provide the movie name as input and the other can find the movie name.

code: #include<stdio.h> #include<string.h> #include<conio.h> int checkflag(int size,char str[size]) {     for(int i=0;str[i]!='\0';i++)     {         if(str[i]=='_')         {             return 1;         }     }     return 0; } int checkkolly(int size,char str[size]) {     for(int i=0;str[i]!='\0';i++)     {         if(str[i]!='*')         {             return 1;         }     }     return 0; } int main() {     char movie_name[100];     printf("\n Enter the movie name(player 1)\n");     scanf(" %[^\n]s",movie_name);     c…
Read more