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");  
  101.             note100 = Convert.ToInt32(Console.ReadLine());  
  102.   
  103.             Console.WriteLine("\n");  
  104.   
  105.             Console.WriteLine("Enter your 50rs Note available");  
  106.             note50 = Convert.ToInt32(Console.ReadLine());  
  107.             Console.WriteLine("\n");  
  108.   
  109.             Console.WriteLine("Enter your 20rs Note available");  
  110.             note20 = Convert.ToInt32(Console.ReadLine());  
  111.             Console.WriteLine("\n");  
  112.   
  113.             Console.WriteLine("Enter your 10rs Note available");  
  114.             note10 = Convert.ToInt32(Console.ReadLine());  
  115.             Console.WriteLine("\n");  
  116.   
  117.             Console.WriteLine("Enter your 5rs Note available");  
  118.             note5 = Convert.ToInt32(Console.ReadLine());  
  119.             Console.WriteLine("\n");  
  120.   
  121.             Console.WriteLine("Enter your 1rs Note available");  
  122.             note1 = Convert.ToInt32(Console.ReadLine());  
  123.             Console.WriteLine("\n");  
  124.   
  125.             Console.WriteLine("Enter your 1rs coint available");  
  126.             coin1 = Convert.ToInt32(Console.ReadLine());  
  127.             Console.WriteLine("\n");  
  128.   
  129.   
  130.             Console.WriteLine("Enter the Bill Amount :");  
  131.             billamount = Convert.ToInt32(Console.ReadLine());  
  132.             Console.WriteLine("\n");  
  133.   
  134.   
  135.   
  136.             Console.WriteLine("Enter the Recieved Amount :");  
  137.             recvamount = Convert.ToInt32(Console.ReadLine());  
  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.   
  172.             Console.ReadKey();  
  173.   
  174.   
  175.         }  
  176.     }  
  177. }  
Output Window



Hope, you like it. Thank you for reading, Have a good day.
Next Recommended Reading Merge Sort Algorithm in C#