Coin Exchange Problem

Part A: Greedy Implementation

A functiongreedy change(amount, denominations)that solves the coin exchange problem greedily (i.e., always select the largest coin first). The function should take in a target amount and a list of infinitely available coins (i.e., denominations) as input. The output should be a list of elements where each index represents the count of each denomination.

For example:

>>> greedy_exchange(56, [20, 10, 5, 1]) [2, 1, 1, 1] >>> greedy_exchange(350, [100, 50, 10, 5, 2, 1]) [3, 1, 0, 0, 0, 0] >>> greedy_exchange(12, [9, 6, 5, 1]) [1, 0, 0, 3] 

Note:You may assume that the coin denominations will always be given in descending order.

Part B: Bounded Lists

A functionbounded upper lists(upper bounds)that accepts as argument a list of positive integers of lengthnand returns a list of all lists of lengthnconsisting of non-negative integers with the following property:

?-for listlst, holds for all indicesi, lst[i] <= upper bound[i].

Hint:adapt the enumeration algorithm from the lecture that enumerates bitlists in lexicographic order.

For example,

>>> bounded_lists([1, 1, 2]) [[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], [0, 1, 1], [0, 1, 2], [1, 0, 0], [1, 0, 1], [1, 0, 2], [1, 1, 0], [1, 1, 1], [1, 1, 2]] 

Part C: Brute Force Implementation

Use the function from Part D to another functionbrute force coin exchange(amount, denominations)that finds an optimal solution for a coin exchange problem input. Optimal meaning uses fewest total coins. The inputs to the function are the amount of money we wish to make, and a list of numbers representing the coindenominations.

Hint:What is an upper bound for the number of coins of a specific denomination that can be selected in a feasible solution?

For Example:

>>> brute_force_coin_exchange(15, [10, 7, 6, 1]) [0, 2, 0, 1] 

Part D: Backtracking Implementation

A functionbacktracking exchange(amount, denominations), that uses backtracking to solve the coin optimisation problem. For Example:

>>> backtracking_exchange(56, [20, 10, 5, 1]) [2, 1, 1, 1] >>> backtracking_exchange(12, [9, 6, 5, 1]) [0, 2, 0, 0]