@Wladimir: Let's see. Suppose the coins are c1=11, c2=5, and c3=2. Then a1=10, a2=22, and a3=55 satisfies
a1*c1 = a2*c2 = a3*c3 and a1 < a2 < a3. But the greedy algorithm fails to find change for, e.g., 8. I think you also need the restriction that the smallest coin = 1 if you want to be able to make change for any integral amount. Dave On Oct 5, 10:48 pm, Wladimir Tavares <[email protected]> wrote: > the greedy algorithm yields an optimal solution for the coin problem when > > c1, c2,c3, ..., ck in decreasing order where ci is value of the coin > > a1*c1 = a2*c2 = a3*c3 = a4*c4 = ... = ak*ck > > a1 < a2 < a3 < ... < ak > > 1*50= 5*10 = 10*5 = 50*1 > > satisfy this condition. > > I think this condition is necessary and suficient for greedy algorithm. > > Wladimir Araujo > Tavareshttp://www.si.ufc.br/~wladimir<http://www.si.ufc.br/%7Ewladimir/> > "Fiz uma faculdade! Só não fiz a segunda porque acabaram os tijolos." > > On Tue, Oct 5, 2010 at 11:05 PM, preethi lakshmi > <[email protected]>wrote: > > > > > show tht the greedy algorithm always yeilds an optimal solution??/ > > > On Tue, Oct 5, 2010 at 7:47 PM, sharad kumar <[email protected]>wrote: > > >> int denom(int Coin[],int n,int amount) > >> { > >> for(i=0;i<n;++i) > >> { > >> c=Coin[i]; > >> for(j=c;j<=amount;++j) > >> { > >> den[j]+=d[j-c]; > >> } > >> } > >> return den[amount]; > >> } > > >> On Wed, Oct 6, 2010 at 4:43 AM, pre lak <[email protected]> wrote: > > >>> Hi all, > > >>> Pls help me with the solution to the following problem related to the > >>> coin changing problem. > > >>> suppose that the available coins a ein the denominations c^0, c^1 , > >>> c^2... c^k for some intgers c>1 and k>=1. show tht the greedy algorithm > >>> always yeilds an optimal solution > > >>> thanks in advance > >>> Preethi > > >>> -- > >>> You received this message because you are subscribed to the Google Groups > >>> "Algorithm Geeks" group. > >>> To post to this group, send email to [email protected]. > >>> To unsubscribe from this group, send email to > >>> [email protected]<algogeeks%2bunsubscr...@googlegroups.com> > >>> . > >>> For more options, visit this group at > >>>http://groups.google.com/group/algogeeks?hl=en. > > >> -- > >> yezhu malai vaasa venkataramana Govinda Govinda > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to [email protected]. > >> To unsubscribe from this group, send email to > >> [email protected]<algogeeks%2bunsubscr...@googlegroups.com> > >> . > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
