Traveling Salesperson Problem · Example 1
A cashier rings up a sale for $4.63 cents in U.S. currency. The customer pays with a $5 bill. The cashier would like to give the customer $0.37 in change using the fewest coins possible. The coins that can be used are quarters ($0.25), dimes ($0.10), nickels ($0.05), and pennies ($0.01). The cashier starts by selecting the coin of highest value less than or equal to $0.37, which is a quarter. This leaves \ 0.37 - $ 0.25 = $ 0.12. The cashier selects the coin of highest value less than or equal to \0.12, which is a dime. This leaves \ 0.12 - $ 0.10 = $ 0.02. The cashier selects the coin of highest value less than or equal to \0.02, which is a penny. This leaves \ 0.02 - $ 0.01 = $ 0.01. The cashier selects the coin of highest value less than or equal to \0.01, which is a penny. This leaves no remainder. The cashier used one quarter, one dime, and two pennies, which is four coins. Use this information to answer the following questions.
(a) Is the cashier’s approach an example of a greedy algorithm or a brute force algorithm? Explain how you know.
(b) The cashier’s solution is the best solution. In other words, four is the fewest number of coins possible. Is this consistent with the results of an algorithm of this kind? Explain your reasoning.
OpenStax, Contemporary Mathematics · §12.9 Traveling Salesperson Problem · Example 1
No hints for this one.
Check your full solution
Attach photos of your pages (up to 3) or one PDF — or check what you typed above. Lemma reads the work and verifies the reasoning, not just the answer.
Your first check today doesn't need an account.
Your photos and PDFs are read once and not stored — only the transcription is kept.