# Making Change Problem Using Greedy Algorithm Using C#

In my previous blog– Making a Change in Greedy, I explained you how we can deal with a Greedy algorithm by making a change example. Today, we will see its program in C#, where I had taken a set of {100, 50, 20, 10, 5 and 1} and our aim is to include a method to input the purchase amount and the amount given by the customer as well as a method to output the amount of change and breakdown by denomination. Apply Greedy algorithm at the cashier side; i.e give fewer numbers of coins to satisfy the Greedy algorithm.

Algorithm

MAKE-CHANGE (n)
C ← {100, 20, 10, 5, 1} // constant.
Sol ← {}; // set that will hold the solution set.
Sum ← 0 sum of item in solution set
WHILE sum not = n
x = largest item in set C such that sum + x ≤ n
IF no such item THEN
RETURN "No Solution"
S ← S {value of x}
sum ← sum + x
RETURN S

Making a Change Problem in C#

Step 1

Open your Visual Studio. By pressing Ctrl +Shift + N, you will get your “New Project” Window.

Step 2

After pressing OK, you will get into your coding part, where you will see three files in Solution Explorer [Properties, References, Program.cs], in which Program.cs file is your main file, where you embed all your making a change program code.

1. using System;
2. using System.Collections.Generic;
3. using System.Linq;
4. using System.Text;
5.
6. namespace ConsoleApplication1 {
7.     class Program {
8.
9.         static int note100, return100, note50, return50, note20, return20, note10, return10,
10.         note5, return5, note1, return1, coin1, returncoins;
11.         static int billamount = 0, recvamount = 0, differ = 0, change = 0;
12.
13.
14.
15.         private static void calcNumberNotes() {
16.             int differ = 0;
17.
18.             differ = recvamount - billamount;
19.
20.
21.             return100 = (int)(Math.Floor(differ / 100 m));
22.             if (return100 > note100) {
23.                 differ = differ - (note100 * 100);
24.                 return100 = note100;
25.             } else {
26.                 differ = differ - (return100 * 100);
27.
28.             }
29.
30.
31.             return50 = (int)(Math.Floor(differ / 50 m));
32.             if (return50 > note50) {
33.                 differ = differ - (note50 * 50);
34.                 return50 = note50;
35.             } else {
36.                 differ = differ - (return50 * 50);
37.
38.             }
39.
40.
41.             return20 = (int)(Math.Floor(differ / 20 m));
42.             if (return20 > note20) {
43.                 differ = differ - (note20 * 20);
44.                 return20 = note20;
45.             } else {
46.                 differ = differ - (return20 * 20);
47.
48.             }
49.
50.
51.
52.             return10 = (int)(Math.Floor(differ / 10 m));
53.             if (return10 > note10) {
54.                 differ = differ - (note10 * 10);
55.                 return10 = note10;
56.             } else {
57.                 differ = differ - (return10 * 10);
58.
59.             }
60.
61.
62.             return5 = (int)(Math.Floor(differ / 5 m));
63.             if (return5 > note5) {
64.                 differ = differ - (note5 * 5);
65.                 return5 = note5;
66.             } else {
67.                 differ = differ - (return5 * 5);
68.
69.             }
70.
71.
72.             return1 = (int)(Math.Floor(differ / 1 m));
73.             if (return1 > note1) {
74.                 differ = differ - (note1 * 1);
75.                 return1 = note1;
76.             } else {
77.                 differ = differ - (return1 * 1);
78.
79.             }
80.
81.             if (differ <= coin1) {
82.
83.                 returncoins = differ;
84.
85.             } else {
86.
87.                 returncoins = -1;
88.
89.             }
90.
91.         }
92.
93.
94.
95.         static void Main(string[] args) {
96.
97.
98.             note100 = note50 = note20 = note10 = note5 = note1 = coin1 = 0;
99.
100.             Console.WriteLine("Enter your 100rs Note available");
102.
103.             Console.WriteLine("\n");
104.
105.             Console.WriteLine("Enter your 50rs Note available");
107.             Console.WriteLine("\n");
108.
109.             Console.WriteLine("Enter your 20rs Note available");
111.             Console.WriteLine("\n");
112.
113.             Console.WriteLine("Enter your 10rs Note available");
115.             Console.WriteLine("\n");
116.
117.             Console.WriteLine("Enter your 5rs Note available");
119.             Console.WriteLine("\n");
120.
121.             Console.WriteLine("Enter your 1rs Note available");
123.             Console.WriteLine("\n");
124.
125.             Console.WriteLine("Enter your 1rs coint available");
127.             Console.WriteLine("\n");
128.
129.
130.             Console.WriteLine("Enter the Bill Amount :");
132.             Console.WriteLine("\n");
133.
134.
135.
136.             Console.WriteLine("Enter the Recieved Amount :");
138.             Console.WriteLine("\n");
139.
140.             Console.WriteLine("The Bill Amount is:- \t" + billamount);
141.             Console.WriteLine("\n");
142.
143.             Console.WriteLine("The Recieved Amount is:- \t" + recvamount);
144.             Console.WriteLine("\n");
145.
146.
147.             calcNumberNotes();
148.
149.
150.             if (returncoins < 0) {
151.                 Console.WriteLine("Changes are not Available");
152.             } else {
153.                 Console.WriteLine("\n");
154.                 change = recvamount - billamount;
155.                 Console.WriteLine("Changes Available Are:- \t" + change);
156.             }
157.
158.
159.
160.
161.             Console.WriteLine("\n");
162.
163.
164.             Console.WriteLine("Notes of 100:\t" + return100);
165.             Console.WriteLine("Notes of 50:\t" + return50);
166.             Console.WriteLine("Notes of 20:\t" + return20);
167.             Console.WriteLine("Notes of 10:\t" + return10);
168.             Console.WriteLine("Notes of 5:\t" + return5);
169.             Console.WriteLine("Notes of 1:\t" + return1);
170.             Console.WriteLine("Coins:\t" + returncoins);
171.