0

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 .

  • We will always get the amount of money we need in minimal coins number when we always pick the maximal coin that smaller from the amount.

Thank you.

1 Answer 1

3

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.