Change Making

The change problem is a fundamental problem in algorithms and combinatorial optimization. It consists of determining, for a given sum and a set of coin or banknote values, a combination that represents that exact sum using the minimum number of units.

To give change for 67 cents using 1, 2, 5, 10, 20, and 50 cent coins, an optimal solution is 50 + 10 + 5 + 2, using 4 coins.

A greedy algorithm for giving change consists of choosing, at each step, the highest possible coin or bill value that does not exceed the remaining amount.

This strategy is simple and efficient, but it does not always guarantee an optimal solution.

A money system is said to be canonical if the greedy algorithm always provides a solution using the minimum number of coins.

When the system is not canonical, the greedy algorithm is not suitable and another approach is needed.

Dynamic programming allows us to solve the change-giving problem optimally for any coin system, by exploiting the fact that an optimal solution for a given sum is built from optimal solutions for smaller sums.

The key steps are as follows:

1 - Initialization: Create an array dp where dp[i] represents the minimum number of coins needed to give change for sum i. Initialize dp[0] = 0 and dp[i] to infinity for i > 0.

2 - Filling: For each sum i from 1 to the target_sum, and for each piece c, apply step 3.

3 - If c <= i, then dp[i] = min(dp[i], dp[i - c] + 1)

4 - The value dp[target_sum] gives the minimum number of pieces needed.

This approach guarantees optimality at the cost of higher computational efficiency.