The classical coin-changing problem can be stated as follow:
Given an integer set C={c_1, c_2, ... c_n} where c_1=1 and c_i < c_{i
+1}, and an positive integer M,
find the minimum of \sum_{i=1}^n x_i, where all x_i's are non-negative
integers and subject to \sum_{i=1}^n x_i c_i = MAnd it is well known that the problem can be solved by dynamic programming. Further, in some special cases a greedy strategy also works. So my question is for what kind of C (the coin system) the problem stated above can only be done by dp, and in what cases the other method can also be adopted. Thank you. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
