I have a question about problem 2 of this homework set and its solution. The task is to show whether the greedy algorithm works or not for the Nephite coinage system from the Book of Mormon (with coins of size 1/8, 1/4, 1/2, 1, 3/2, 2, 4, and 7). In the solution given, the professor states that you only need to check if the algorithm works for small values, as all higher values are combinations of these.

My question is, in a coinage system with a coin of largest value $n$, how many values for the greedy algorithm do you have to check before you are assured that the greedy algorithm is efficient?

Note: This question is similar to this post.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.