>
> It was acknowledged that "OP's problem doesn't need this" so I assume
> the question was to think about it more generally somehow.
>
While we're on wild tangents...
We should probably note, since it hasn't been mentioned yet, that the
generalized problem with arbitrary coin choices is classically known
as the change-making problem:
https://en.wikipedia.org/wiki/Change-making_problem
which is one of the core examples used when teaching the
dynamic-programming algorithm technique.
The reason we don't need dynamic-programming for the original poster's
question is because the "greedy" algorithm works on US and modern UK
denominations, because the coin set is "canonical", in the sense
described in David Pearson's "A Polynomial-time Algorithm for the
Change-Making Problem". More details in:
http://cs.stackexchange.com/questions/6552/when-can-a-greedy-algorithm-solve-the-coin-change-problem
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
