Answered: The classic example of following a…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

The classic example of following a greedy algorithm is making change. Let’s
say you buy some items at the store and the change from your purchase is
63 cents. How does the clerk determine the change to give you? If the clerk
follows a greedy algorithm, he or she gives you two quarters, a dime, and
three pennies. That is the smallest number of coins that will equal 63 cents
(given that we don’t allow fifty-cent pieces).
It has been proven that an optimal solution for coin changing can always
be found using the current American denominations of coins. However, if we
introduce some other denomination to the mix, the greedy algorithm doesn’t
produce an optimal solution.
Write a program that uses a greedy algorithm to make change (this code
assumes change of less than one dollar):

Expert Solution

Step by step

Solved in 3 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions