CS 514, Algorithms, Spring 2025
Optional HW7 (1% extra credit)
Due Monday 5/19 at 9:59pm.

Many students didn't do very well on the final DP problem: number of coins.
So you now have the option of redoing it for 1% extra credit.
It's totally optional though.

You only need to submit coins.py and it will be graded.

flip $ /nfs/guille/huang/cs514/submit 514 hw7 coins.py

A foreign country has n types of coins, each with value v_i cents (i=1~n), 
and we'd like to make up an exact amount of X cents with these coins 
(X and v_i's are positive integers). 
We want to minimize the total number of coins used. 
E.g., for X = 5, v = [1, 3], the optimal solution is 3 coins (5=1+1+3).

Your coins.py should include a function smallest(X, v) which returns a pair (b, sol)
where b is the minimum number of coins and sol is a list of coins. If it's impossible
to make up X cents, then return (0, []).

>>> smallest(5, [1,3])
(3, [3, 1, 1])

>>> smallest(5, [3,4])
(0, [])

>>> smallest(6, [1,3,4])
(2, [3, 3])

>>> smallest(87, [1,5,10,25])
(6, [25, 25, 25, 10, 1, 1])

>>> smallest(123, [2, 4, 8])
(0, [])

Tie-breaking: arbitrary; don't worry about it.
Either top-down or bottom-up is fine.