Ask Question

Suppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm NOT produce an optimal answer?

a) 20

b) 12

c) 6

d) 5

+3
Answers (1)
  1. 16 August, 09:09
    0
    The correct option is C

    Explanation:

    A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.

    In this, three coins {4,1,1} will be selected to make a sum of 6. But, the optimal answer is two coins {3,3}.
Know the Answer?
Not Sure About the Answer?
Find an answer to your question 👍 “Suppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is ...” in 📗 Computers & Technology if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers