How to use dynamic programming to solve this?

Question

Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies and toonies you have. Assume that you have enough coins to pay x cents. You do not have to pay exactly x cents; you can pay more. The cashier is assumed to be smart enough to give you back the optimal number of coins as change. We want to minimize the number of coins that changes hands, that is the number of coins you give to the cashier plus the number of coins the cashier gives back to you.

For example, if we want to pay 99 cents and we have 99 pennies and 1 loonie, then the optimal solution would be to give the cashier the loonie and take back 1 penny.

A particularly easy solution that occurs to me is to create a six-dimensional array. But in practice this is not feasible. So I am wondering if anyone can give me a small hint as to how to use dynamic programming to solve this (as this question looks intuitively to me like a DP problem). Once I have a hint, I can perhaps work out the remaining details myself. Thanks.

Answer 1

This is the famous change-making problem.

If you want to solve it with dynamic programming, you have to come up with a suitable recursion. The central question is:

Assuming you know the optimal coin choices for all $k < n$ (cents), how do you derive the optimal choice of coins for $n$ (cents)?

Answer 2

That looks to me as an instance of the Bounded Knapsack Problem, where there's a limited number of copies of each kind of item, turning the usual maximization of value into a minimization (you want to minimize the total number of coins given, within the possibilities entailed by the coins you have at hand).