CODEWITHSUNDEEP
algorithmgreedy
Bobbbaa
Bobbbaa

Reputation: 199

Greedy algorithm and coins algorithm

First, yes it's my HW and I find it hard so I'll really appreciate some guidance.

I need to prove that for denomination of 1,x,x2...xn when x>=1 the greedy algorithm for the coins problem always work .

Thank you.

Upvotes: 0

Views: 530

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

As this is your homework I will not provide a complete answer but will rather try to guide you:

First as it usually happens for problems of that type try and prove for yourself that the statement is true for the first few natural numbers. Try to summarize what you use to make the proof for them. This usually will give you some guidance of the correct approach.

I would use induction for this one.

Another option that might help you - represent all the numbers in numerical system with base x. This should make it clearer why the statement is true.

Hope this helps you.

Upvotes: 3

Related Questions