**Author: **Shehzad Hemani

Download Source Code : 1064_sourceCode.zip

In this simple article you will know how you can make solution of coin change problem by using greedy algorithm in vb and C #.net.

**Coin Change Problem:**

Problem: Return correct change using a minimum number of coins. The coin problem is a mathematical problem that asks what is the largest monetary amount that cannot be obtained using only coins of specified denominations. For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set.

**Greedy Algorithm:**

A greedy algorithm works in phases. At each phase:

a. You take the best you can get right now, without regard for future consequences

b. You hope that by choosing a *local* optimum at each step, you will end up at a *global* optimum

A greedy algorithm typically makes (approximately) n choices for a problem of size n (The first or last choice may be forced).

Hence the expected running time is: O (n * O (choice (n))), where choice (n) is making a choice among n objects.

**Elements of the Greedy Strategy:**

Cast problem as one in which we make a greedy choice and are left with one sub problem to solve.

To show optimality:

- Prove there is always an
**optimal solution** to original problem that makes the greedy choice.

2. Solution to original problem. Demonstrate that what remains is a sub problem with property: If we combine the optimal solution of the sub problem with the greedy choice we have an optimal

**Working of the Greedy Strategy:**

Greedy algorithm just check the next best choice whether it leads to the solution or not. The problem with this approach is that it may select a choice which is the local minima and it may stuck in the local optima. Greedy algorithm will work properly if the local maximum is equal to the global maxima.

For the solution, we write a recursive function which takes the array of denominations and the amount for which you want the change.

To demonstrate make a new window application. Drag one button and one text box on the form and write the following code:

C#:

private void btn_amount_Click(object sender, EventArgs e)

{

int[] arr = {1,2,5,10 };

int amount;

int change;

amount = Convert.ToInt16(txt_amount.Text);

change=GetChange(amount, arr);

MessageBox.Show("number of coins for change= "+Convert.ToString(change));

}

VB:

Private Sub btn_amount_Click(ByVal sender As Object, ByVal e As EventArgs)

Dim arr As Integer() = {1, 2, 5, 10}

Dim amount As Integer

Dim change As Integer

amount = Convert.ToInt16(txt_amount.Text)

change = GetChange(amount, arr)

MessageBox.Show("number of coins for change= " & Convert.ToString(change))

End Sub

And the recursive function for the solution is given as:

C#:

public int GetChange(int amount, int[] coins)

{

if (amount == 0)

{

return 0;

}

for (int i = 4; i > 0; i--)

{

int coin = coins[i - 1];

if (amount >= coin)

{

MessageBox.Show(Convert.ToString(coin), "");

return (1 + GetChange(amount - coin, coins));

}

}

return 0;

}

VB:

Public Function GetChange(ByVal amount As Integer, ByVal coins As Integer()) As Integer

If amount = 0 Then

Return 0

End If

For i As Integer = 4 To 1 Step -1

Dim coin As Integer = coins(i - 1)

If amount >= coin Then

MessageBox.Show(Convert.ToString(coin), "")

Return (1 + GetChange(amount - coin, coins))

End If

Next

Return 0

End Function

Now write the following code on FORM LOAD event:

**C#:**

private void Form1_Load(object sender, EventArgs e)

{

this.Text = "DEVASP APPLICATION";

}

VB:

Private Sub Form1_Load(ByVal sender As Object, ByVal e As EventArgs)

Me.Text = "DEVASP APPLICATION"

End Sub

**This simple article tells ****how you can make solution of coin change problem by using greedy algorithm in vb and C #.net.**