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

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

Answer Link

busyfingers1193 busyfingers1193 · Answer 2 · 2020-03-31T04:27:09+02:00

busyfingers1193 busyfingers1193

31-03-2020

Answer:

C) 6

Explanation:

Answer Link

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

Respuesta :

Otras preguntas

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