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;
  6. namespace ConsoleApplication1 {
  7. class Program {
  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;
  15. private static void calcNumberNotes() {
  16. int differ = 0;
  18. differ = recvamount - billamount;
  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);
  28. }
  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);
  38. }
  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);
  48. }
  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);
  59. }
  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);
  69. }
  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);
  79. }
  81. if (differ <= coin1) {
  83. returncoins = differ;
  85. } else {
  87. returncoins = -1;
  89. }
  91. }
  95. static void Main(string[] args) {
  98. note100 = note50 = note20 = note10 = note5 = note1 = coin1 = 0;
  100. Console.WriteLine("Enter your 100rs Note available");
  101. note100 = Convert.ToInt32(Console.ReadLine());
  103. Console.WriteLine("\n");
  105. Console.WriteLine("Enter your 50rs Note available");
  106. note50 = Convert.ToInt32(Console.ReadLine());
  107. Console.WriteLine("\n");
  109. Console.WriteLine("Enter your 20rs Note available");
  110. note20 = Convert.ToInt32(Console.ReadLine());
  111. Console.WriteLine("\n");
  113. Console.WriteLine("Enter your 10rs Note available");
  114. note10 = Convert.ToInt32(Console.ReadLine());
  115. Console.WriteLine("\n");
  117. Console.WriteLine("Enter your 5rs Note available");
  118. note5 = Convert.ToInt32(Console.ReadLine());
  119. Console.WriteLine("\n");
  121. Console.WriteLine("Enter your 1rs Note available");
  122. note1 = Convert.ToInt32(Console.ReadLine());
  123. Console.WriteLine("\n");
  125. Console.WriteLine("Enter your 1rs coint available");
  126. coin1 = Convert.ToInt32(Console.ReadLine());
  127. Console.WriteLine("\n");
  130. Console.WriteLine("Enter the Bill Amount :");
  131. billamount = Convert.ToInt32(Console.ReadLine());
  132. Console.WriteLine("\n");
  136. Console.WriteLine("Enter the Recieved Amount :");
  137. recvamount = Convert.ToInt32(Console.ReadLine());
  138. Console.WriteLine("\n");
  140. Console.WriteLine("The Bill Amount is:- \t" + billamount);
  141. Console.WriteLine("\n");
  143. Console.WriteLine("The Recieved Amount is:- \t" + recvamount);
  144. Console.WriteLine("\n");
  147. calcNumberNotes();
  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. }
  161. Console.WriteLine("\n");
  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);
  172. Console.ReadKey();
  175. }
  176. }
  177. }
Output Window



Hope, you like it. Thank you for reading, Have a good day.