6) a) In the Coin changing problem, we have to give change for n rupees using th

Question

6) a) In the Coin changing problem, we have to give change for n rupees using the least number of coins of a given set of denominations. It is clear that we cannot give change for any n for all set of denominations. For example, trivially, we cannot give change for . 3, if no 1, 2 or 3 rupees coins do not exist or not included in the allowed denominations. If the set of denominations include l then we can always give change, so that there is a way of changing n for any n. We can use greedy approach to find the optimal solutions for many set of denominations. Show that, however, there are set of denominations for which we cannot find the optimal solution by greedy approach. You should include l in your denominations so that a solution always exists for the problem.

Explanation / Answer

program:--

/*
in this coin changing program I am taking Rs. 1 2 5 10 20 50 100 200 500 1000
are as available denominations
*/
#include <iostream>
using namespace std;
int main()
{
   int n, flag=0, n1s=0, n2s=0, n5s=0, n10s=0, n20s=0, n50s=0, n100s=0, n200s=0, n500s=0, n1000s=0;
   do{
       cout<<"Enter n value: "<<endl;
       cin>>n;   //read n value for change
       cout<<"Change for given N value is"<<endl;
       if (n>1000)   //calculate number of 1000s to be give
       {
           flag=1;   //change is given flag set to 1
           n1000s=n/1000;
           n=n%1000;
           cout<<"Number of Rs 1000 coins are: "<<n1000s<<endl;
       }
       if ((n>=500&&flag==1)||n>500)   //calculate number of 500s to be give
       {
           flag=1;   //change is given flag set to 1
           n500s=n/500;
           n=n%500;
           cout<<"Number of Rs 500 coins are: "<<n500s<<endl;
       }
       if ((n>=200&&flag==1)||n>200)   //calculate number of 200s to be give
       {
           flag=1;   //change is given flag set to 1
           n200s=n/200;
           n=n%200;
           cout<<"Number of Rs 200 coins are: "<<n200s<<endl;
       }
       if ((n>=100&&flag==1)||n>100)   //calculate number of 100s to be give
       {
           flag=1;   //change is given flag set to 1
           n100s=n/100;
           n=n%100;
           cout<<"Number of Rs 100 coins are: "<<n100s<<endl;
       }
       if ((n>=50&&flag==1)||n>50)   //calculate number of 50s to be give
       {
           flag=1;   //change is given flag set to 1
           n50s=n/50;
           n=n%50;
           cout<<"Number of Rs 50 coins are: "<<n50s<<endl;
       }
       if ((n>=20&&flag==1)||n>20)   //calculate number of 20s to be give
       {
           flag=1;   //change is given flag set to 1
           n20s=n/20;
           n=n%20;
           cout<<"Number of Rs 20 coins are: "<<n20s<<endl;
       }
       if ((n>=10&&flag==1)||n>10)   //calculate number of 10s to be give
       {
           flag=1;   //change is given flag set to 1
           n10s=n/10;
           n=n%10;
           cout<<"Number of Rs 10 coins are: "<<n10s<<endl;
       }
       if ((n>=5&&flag==1)||n>5)   //calculate number of 5s to be give
       {
           flag=1;   //change is given flag set to 1
           n5s=n/5;
           n=n%5;
           cout<<"Number of Rs 5 coins are: "<<n5s<<endl;
       }
       if ((n>=2&&flag==1)||n>2)   //calculate number of 2s to be give
       {
           flag=1;   //change is given flag set to 1
           n2s=n/2;
           n=n%2;
           cout<<"Number of Rs 2 coins are: "<<n2s<<endl;
       }
       if ((n>=1&&flag==1)||n>=1)   //calculate number of 1s to be give
       {
           flag=1;   //change is given flag set to 1
           n1s=n/1;
           n=n%1;
           cout<<"Number of Rs 1 coins are: "<<n1s<<endl;
       }
       int total=n1s+n2s+n5s+n10s+n20s+n50s+n100s+n200s+n500s+n1000s;
       cout<<"Total number of coins given is: "<<total<<endl;
       //n, flag and denomination values are reset after the change given
       n=1; flag=0; n1s=0; n2s=0; n5s=0; n10s=0; n20s=0; n50s=0; n100s=0; n200s=0; n500s=0; n1000s=0;
       cout<<endl;
   }while(n>0);
   return 0;
}

Output:--

Enter n value:
1
Change for given N value is
Number of Rs 1 coins are: 1
Total number of coins given is: 1

Enter n value:
2
Change for given N value is
Number of Rs 1 coins are: 2
Total number of coins given is: 2

Enter n value:
3
Change for given N value is
Number of Rs 2 coins are: 1
Number of Rs 1 coins are: 1
Total number of coins given is: 2

Enter n value:
4
Change for given N value is
Number of Rs 2 coins are: 2
Total number of coins given is: 2

Enter n value:
5
Change for given N value is
Number of Rs 2 coins are: 2
Number of Rs 1 coins are: 1
Total number of coins given is: 3

Enter n value:
6
Change for given N value is
Number of Rs 5 coins are: 1
Number of Rs 1 coins are: 1
Total number of coins given is: 2

Enter n value:
7
Change for given N value is
Number of Rs 5 coins are: 1
Number of Rs 2 coins are: 1
Total number of coins given is: 2

Enter n value:
8
Change for given N value is
Number of Rs 5 coins are: 1
Number of Rs 2 coins are: 1
Number of Rs 1 coins are: 1
Total number of coins given is: 3

Enter n value:
9
Change for given N value is
Number of Rs 5 coins are: 1
Number of Rs 2 coins are: 2
Total number of coins given is: 3

Enter n value:
10
Change for given N value is
Number of Rs 5 coins are: 2
Total number of coins given is: 2

Enter n value:
50
Change for given N value is
Number of Rs 20 coins are: 2
Number of Rs 10 coins are: 1
Total number of coins given is: 3

Enter n value:
51
Change for given N value is
Number of Rs 50 coins are: 1
Number of Rs 1 coins are: 1
Total number of coins given is: 2

Enter n value:
99
Change for given N value is
Number of Rs 50 coins are: 1
Number of Rs 20 coins are: 2
Number of Rs 5 coins are: 1
Number of Rs 2 coins are: 2
Total number of coins given is: 6

Enter n value:
100
Change for given N value is
Number of Rs 50 coins are: 2
Total number of coins given is: 2

Enter n value:
202
Change for given N value is
Number of Rs 200 coins are: 1
Number of Rs 2 coins are: 1
Total number of coins given is: 2

Enter n value:
500
Change for given N value is
Number of Rs 200 coins are: 2
Number of Rs 100 coins are: 1
Total number of coins given is: 3

Enter n value:
495
Change for given N value is
Number of Rs 200 coins are: 2
Number of Rs 50 coins are: 1
Number of Rs 20 coins are: 2
Number of Rs 5 coins are: 1
Total number of coins given is: 6

Enter n value:
1000
Change for given N value is
Number of Rs 500 coins are: 2
Total number of coins given is: 2

Enter n value:
9999
Change for given N value is
Number of Rs 1000 coins are: 9
Number of Rs 500 coins are: 1
Number of Rs 200 coins are: 2
Number of Rs 50 coins are: 1
Number of Rs 20 coins are: 2
Number of Rs 5 coins are: 1
Number of Rs 2 coins are: 2
Total number of coins given is: 18

Enter n value:

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.