What is the ans to the following ques??
Can greedy be used to find the minimum number of notes to make 1000 from (1,5, 7 ) rupee notes.
Doubt in quiz ques
the answer is yes
how to get to this
1000/7 = 142
142*7 = 994
from 994 u can pick the next greater note which is 5 and from 5 u can go to 1
there is no generalisation as such when is greedy going to fail
but it usually fails when the number u can pick next is not the immediate next greater to the element u picked last and going to to immediate next greater and calculating from that state is more optimum than reaching the current state
which does not happen in this case so, greedy works for it