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

Answer 1

C) 6

Step-by-step explanation:

Answer 2

The correct option is C

Step-by-step 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}.