Utility Mill

This is useful for making change. This is a classic dynamic programming problem.

The greedy solution is very direct and fast, and will produce an optimal solution for the denominations used in the U.S. and most world currencies, but there exist sets of denominations for which it will not produce an optimal solution.

The non-greedy solution uses dynamic programmimg. It will always produce an optimal solution. It uses space and time proportional to the value times the number of denominations, so it will be slow for very large values.