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

Question

Computers and Technology

Irwin

12 December, 22:07

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)

Know the Answer?

Makhi Levine · Answer 1

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}.

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) 20b) 12c) 6d) 5

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