Discrete Mathematics and its Applications : Greedy Algorithms
Not what you're looking for?
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.
Purchase this Solution
Solution Summary
Greedy Algorithms are investigated. The solution is detailed and well presented.
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: ...
Purchase this Solution
Free BrainMass Quizzes
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.
Geometry - Real Life Application Problems
Understanding of how geometry applies to in real-world contexts
Graphs and Functions
This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.
Solving quadratic inequalities
This quiz test you on how well you are familiar with solving quadratic inequalities.
Probability Quiz
Some questions on probability