Share
Explore BrainMass

Discrete Mathematics and its Applications : Greedy Algorithms

Greedy Algorithms

procedure change (c1, c2, ...., cr: values of denominations of coins, where c1 > c2 > ... > cr; n: a positive integer)
for i : = 1 to r
while n ≥ ci
begin
add a coin with value ci to the change
n :=n - ci
end

2. Use the greedy algorithm to make change using quarters, dimes, nickels, and pennies for:
a) 87 cents.
b) 49 cents.
c) 99 cents.
d) 33 cents.

Please see the attached file for the fully formatted problems.

Attachments

Solution Preview

Hello and thank you for posting your question to Brainmass!

The solution is attached below in two Word XP Format, while the other is in Adobe pdf format. Therefore you can choose the format that is most suitable to you.

The output is pretty self explanatory. I added the Visual Basic algorithm at th eend of the file.

It requires a form with one button, one textbox and one rich text box.

Greedy Algorithms

c1=25 c2=10 c3=5 c4=1

87 cents:

Initial Amount87
=============================
Step: 1 (i= 1)
Coin Denomination: 25
Number of coins of this denomination: 1
Current Change Left: 62
------------------------------------
Step: 2 (i= 1)
Coin Denomination: 25
Number of coins of this denomination: 2
Current Change Left: 37
------------------------------------
Step: 3 (i= 1)
Coin Denomination: 25
Number of coins of this denomination: 3
Current Change Left: 12
------------------------------------
Step: 4 (i= 2)
Coin Denomination: 10
Number of coins of this denomination: 1
Current Change Left: 2
------------------------------------
Step: 5 (i= 4)
Coin Denomination: 1
Number of coins of this denomination: 1
Current Change Left: 1
------------------------------------
Step: 6 (i= 4)
Coin Denomination: 1
Number of coins of this denomination: 2
Current Change Left: 0
------------------------------------
Final Distribution of Coins
25: 3 10: 1 5: 0 1: 2

Initial Change Amount: 49
=============================
Step: 1 (i= 1)
Coin Denomination: 25
Number of coins of this denomination: 1
Change left: ...

Solution Summary

Greedy Algorithms are investigated. The solution is detailed and well presented.

$2.19