Question 2.2 Suppose you are a simple shopkeeper living in a…

Question Answered step-by-step Question 2.2 Suppose you are a simple shopkeeper living in a… Question 2.2 Suppose you are a simple shopkeeper living in a country with n different types of coins, with values 1 = c[1] < c[2] < ··· < c[n]. (In the U.S., for example, n = 6 and the values are 1, 5, 10, 25, 50 and 100 cents.) Your beloved and benevolent dictator, El Generalissimo, has decreed that whenever you give a customer change, you must use the smallest possible number of coins, so as not to wear out the image of El Generalissimo lovingly engraved on each coin by servants of the Royal Treasury.(a) In the United States, there is a simple greedy algorithm that always results in the smallest number of coins: subtract the largest coin and recursively give change for the remainder. El Generalissimo does not approve of American capitalist greed. Show that there is a set of coin values for which the greedy algorithm does not always give the smallest possible of coins. Engineering & Technology Computer Science ITCS 532 Share QuestionEmailCopy link Comments (0)