From optimization to approximate approaches
Reading time10 minIn brief
Article summary
This article covers optimization problems and the change-making problem, demonstrating how dynamic programming and greedy algorithms can be applied. We also discuss how a greedy heuristic can be used to approximate a solution to that problem. The article concludes with a comparison of these approaches and their trade-offs.
Main takeaways
-
Finding exact solutions to optimization problems can be very costly, even with dynamic programming.
-
Greedy algorithms can give a solution close to the optimum by locally optimizing a function iteratively instead of once globally.
-
Sometimes, greedy algorithms can provide exact solutions, but not always!
Article contents
1 — Optimization problems
Dynamic programming is often very useful when dealing with optimization problems (see the note on problems). The point is that optimization problems are variants of search problems with many solutions. Intuitively, if the naive computation of one solution already incurs many recomputations, it is going to be worse when looking for the best solution.
Solving an optimization problem using dynamic programming requires to follow the same steps as before, with the constraint that the optimization problem should present an additional property: it should exhibit optimal substructure.
What does it mean? In order to properly apply a divide-and-conquer strategy, we must be able to decompose problems into subproblems and compose the solutions to the subproblems into a solution to the problem. As we want to produce optimal solutions, we need to make sure that by composing the optimal solutions to the subproblems we do obtain the optimal solution to the problem. Also, since there is an underlying search problem, there are choices. A choice can be seen as a new kind of decomposition where the choice is split into its different alternatives. Its cost is then the minimum of its alternative costs.
Let us see how it works with the change making problem.
2 — The change making problem
This problem is a variant of the coin change problem that you have encountered earlier. The input parameters are the same:
- A list of integer values giving the denominations of the available coins and notes in the currency, for instance
[1, 2, 5, 10, 50]for euros. We assume here that these values $v_1$, …, $v_n$ are ordered: $v_1 \lt ... \lt v_n$. - An amount to be changed.
But, whereas the coin change problem looks for the number of ways to change the amount, the change making problem looks for the minimum amount of coins necessary.
2.1 — The coin change problem
Here is a possible code for the coin change problem:
def count_coin_changes (amount: int, coins: list[int]) -> int:
"""
This function calculates the number of ways to make change for a given amount using a list of coins.
In:
* amount: The amount for which change is to be made.
* coins: The list of coins available to make change.
Out:
* The number of ways to make change for the given amount.
"""
# Base cases
if amount == 0:
return 1
if amount < 0 or len(coins) == 0:
return 0
# Recursive calls
with_first_coin = count_coin_changes(amount - coins[0], coins)
without_it = count_coin_changes(amount, coins[1:])
return with_first_coin + without_it
print(count_coin_changes(4, [1, 2, 3])) # 4
print(count_coin_changes(10, [2, 5, 3, 6])) # 5
print(count_coin_changes(3, [2, 5])) # 0public class NbCountChanges {
public static int countCoinChanges(int amount, int[] coins) {
if (amount == 0) {
return 1;
}
if (amount < 0 || coins.length == 0) {
return 0;
}
int[] remainingCoins = new int[coins.length - 1];
System.arraycopy(coins, 1, remainingCoins, 0, coins.length - 1);
int withFirstCoin = countCoinChanges(amount - coins[0], coins);
int withoutFirstCoin = countCoinChanges(amount, remainingCoins);
return withFirstCoin + withoutFirstCoin;
}
public static void main(String[] args) {
System.out.println(countCoinChanges(4, new int[]{1, 2, 3})); // 4
System.out.println(countCoinChanges(10, new int[]{2, 5, 3, 6})); // 5
System.out.println(countCoinChanges(3, new int[]{2, 5})); // 0
}
}2.2 — Back to the change making problem
Implementing a recursive definition of the change making problem is based on the same idea as in the coin change problem: we choose a coin and we use it or not. We could decide, as in the coin change problem, to use the first coin but we are rather going to use the last one. We will see why later.
def change_making (amount, coins) -> int:
"""
This function calculates the minimum number of coins needed to make change for a given amount.
In:
* amount: The amount for which change is to be made.
* coins: The list of coins available to make change.
Out:
* The minimum number of coins needed to make change for the given amount.
"""
# Inner function to initialize utilitary parameters
def __change_making (current_amount, i) -> int:
"""
This helper function calculates recursively the minimum number of coins needed to make change for a given amount.
In:
* current_amount: The amount for which change is to be made.
* i: The index of the coin to be used.
Out:
* The minimum number of coins needed to make change for the given amount.
"""
# Base cases
if current_amount == 0:
return 0
if i == -1 or current_amount < 0:
return float('inf')
# There is the choice of using the ith coin or not
return min(__change_making(current_amount, i - 1), 1 + __change_making(current_amount - coins[i], i))
# Start with the coin of highest denomination
return __change_making(amount, len(coins) - 1)
# Test cases
euros = [1, 2, 5, 10, 50]
assert(change_making(49, euros) == 7) # [0, 2, 1, 4, 0]
assert(change_making(99, euros) == 8) # [0, 2, 1, 4, 1]
print(change_making(99, euros))
print(change_making(49, euros))
old_pounds = [1, 3, 6, 12, 24, 30]
# 49 = 1 + 2 * 24
assert(change_making(49, old_pounds) == 3) # [1, 0, 0, 0, 2, 0]
print(change_making(49, old_pounds))
foo = [2, 5]
assert(change_making(3, foo) == float('inf'))
print(change_making(3, foo))
print('All test cases passed!')public class ChangeMaking {
public static int changeMaking(int amount, int[] coins) {
return changeMakingAux(amount, coins, coins.length - 1);
}
private static int changeMakingAux(int currentAmount, int[] coins, int i) {
if (currentAmount == 0) {
return 0;
} else if (i == -1 || currentAmount < 0) {
return Integer.MAX_VALUE;
} else {
int exclude = changeMakingAux(currentAmount, coins, i - 1);
int include = changeMakingAux(currentAmount - coins[i], coins, i);
if (include != Integer.MAX_VALUE) {
include += 1;
}
return Math.min(exclude, include);
}
}
public static void main(String[] args) {
int[] euros = {1, 2, 5, 10, 50};
assert(changeMaking(49, euros) == 7);
assert(changeMaking(99, euros) == 8);
System.out.println(changeMaking(99, euros));
System.out.println(changeMaking(49, euros));
int[] oldPounds = {1, 3, 6, 12, 24, 30};
assert(changeMaking(49, oldPounds) == 3);
System.out.println(changeMaking(49, oldPounds));
int[] foo = {2, 5};
assert(changeMaking(3, foo) == Integer.MAX_VALUE);
System.out.println(changeMaking(3, foo));
System.out.println("All test cases passed!");
}
}It is straightforward to implement a memoized version of the problem, using either a dictionary or a two-dimensional array. This is left as an exercise to the reader. Let us now turn to dynamic programming.
2.3 — A dynamic programming version of the change making problem
Implementing the dynamic programming version of the change making is based on the idea that the minimum number of coins needed to make change for a given amount can be computed by considering the minimum number of coins needed to make change for smaller amounts. The problem graph is a chain, where each vertex corresponds to a given amount and the edges correspond to the choice of using a coin or not.
def change_making_dp (amount, coins) -> int:
"""
This function calculates, using dynamic programming, the minimum number of coins needed to make change for a given amount.
In:
* amount: The amount for which change is to be made.
* coins: The list of coins available to make change.
Out:
* The minimum number of coins needed to make change for the given amount.
"""
# Initialize the table with infinity for all values except the first column
table = [float('inf')] * (amount + 1)
table[0] = 0
# For each amount greater than or equal to the coin value
for coin in coins:
for i in range(coin, amount + 1):
# check if using the current coin gives a better solution
# i.e., less coins for the amount - coin + 1
table[i] = min(table[i], table[i - coin] + 1)
return table[amount] if table[amount] != float('inf') else -1
# Test the function
print(change_making_dp(11, [1, 2, 5]))
print(change_making_dp(11, [1, 3, 4]))
print(change_making_dp(11, [1, 5, 6]))
print(change_making_dp(11, [1, 2, 5, 10]))public class ChangeMakingDP {
public static int changeMakingDP(int amount, int[] coins) {
// Initialize the table with infinity for all values except the first column
int[] table = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
table[i] = Integer.MAX_VALUE;
}
table[0] = 0;
// for each coin
for (int coin : coins) {
// for each amount greater than or equal to the coin value
for (int i = coin; i <= amount; i++) {
// check if using the current coin gives a better solution (i.e. less coins for the amount - coin + 1)
if (table[i - coin] != Integer.MAX_VALUE) {
table[i] = Math.min(table[i], table[i - coin] + 1);
}
}
}
return table[amount] != Integer.MAX_VALUE ? table[amount] : -1;
}
public static void main(String[] args) {
System.out.println(changeMakingDP(11, new int[]{1, 2, 5}));
System.out.println(changeMakingDP(11, new int[]{1, 3, 4}));
System.out.println(changeMakingDP(11, new int[]{1, 5, 6}));
System.out.println(changeMakingDP(11, new int[]{1, 2, 5, 10}));
}
}3 — Greedy algorithms
Greedy algorithms make choices instead of considering all possibilities. They prune the search by taking good local decisions, computing a local optimum with the risk of missing the global one. Let us consider the change making problem. In the previous versions, we have systematically considered the choice of using or not the coin with the highest denomination. A greedy strategy consists in choosing the coin with the highest denomination as long as it is possible. The intuition is that, locally, it looks more efficient than not using it, by maximally decreasing the amount to be changed with a single coin. As a result, the algorithm may however ignore better solutions that would have been obtained by considering not using it.
The baffling part of it is that the greedy version of the change making problem provides optimal solutions with some currency systems, it is then extremely efficient even with respect to dynamic programming, but ignore optimal solutions with others (that is, it is just incorrect). See the program below.
When aiming at efficiency, a general risk is to:
- Use a dynamic programming strategy when a greedy strategy suffices.
- Use a greedy strategy when a dynamic programming strategy is required (the greedy strategy misses optimal solutions).
Unfortunately, whereas it is fairly easy to show that a greedy algorithm does not work, by finding a counterexample, it is not that easy to show that there is no counterexample.
This requires to be very cautious and ideally make proofs, that a problem exhibits optimal substructure, that a greedy strategy returns optimal solutions.
3.1 — A greedy version of the the change making problem
def greedy_change (amount, coins) -> list[int]:
"""
This function calculates the minimum number of coins needed to make change for a given amount using a greedy strategy.
In:
* amount: The amount for which change is to be made.
* coins: The list of coins available to make change, ordered in increasing order.
Out:
* A list of coin numbers i_1, i_2, ..., i_n such that i_1 * c_1 + i_2 * c_2 + ... = v.
"""
# For each coin from the highest to the lowest
solution = []
for coin in reversed(coins):
# Function divmod returns a tuple with the quotient and the remainder
count, amount = divmod(amount, coin)
solution.append(count)
#Reverse the solution to have the coins in the same order as the input
return solution[::-1]
# Test cases
euros = [1, 2, 5, 10, 50]
print(greedy_change(49, euros)) # [0, 2, 1, 4, 0]
print(greedy_change(99, euros)) # [0, 2, 1, 4, 1]
# The greedy algorithm does not always give the optimal solution
old_pounds = [1, 3, 6, 12, 24, 30]
# 49 = 1 + 6 + 12 + 30 = 1 + 2 * 24
print(greedy_change(49, old_pounds)) # [1, 0, 1, 1, 0, 1]import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class GreedyChange {
public static List<Integer> greedyChange(int amount, List<Integer> coins) {
List<Integer> solution = new ArrayList<>();
//for each coin from the highest to the lowest
for (int i = coins.size() - 1; i >= 0; i--) {
int coin = coins.get(i);
//divmod returns a tuple with the quotient and the remainder
int count = amount / coin;
amount %= coin;
solution.add(count);
}
//reverse the solution to have the coins in the same order as the input
Collections.reverse(solution);
return solution;
}
public static void main(String[] args) {
List<Integer> euros = List.of(1, 2, 5, 10, 50);
System.out.println(greedyChange(49, euros)); // [0, 2, 1, 4, 0]
System.out.println(greedyChange(99, euros)); // [0, 2, 1, 4, 1]
List<Integer> oldPounds = List.of(1, 3, 6, 12, 24, 30);
System.out.println(greedyChange(49, oldPounds)); // [1, 0, 1, 1, 0, 1]
}
}To go further
Looks like this section is empty!
Anything you would have liked to see here? Let us know on the Discord server! Maybe we can add it quickly. Otherwise, it will help us improve the course for next year!
To go beyond
Looks like this section is empty!
Anything you would have liked to see here? Let us know on the Discord server! Maybe we can add it quickly. Otherwise, it will help us improve the course for next year!