Youve just signed up as a software engineer for a new intergalactic trading post in Deep Space 6. For each transaction, you are given a list of coin denomination values, e.g., denomination = [1, 5, 10, 17], and an amount of change, C. You have an unlimited number of each type of coin. Your goal is to find the shortest possible list of coins that adds up to C. For simplicity, assume that there is always a penny 1 ? denomination and that the desired change C is an integer, so the problem always has a solution.

Write a function make_change(denomination, C) which returns a list of coins that add up to C, where the size of the list is as small as possible. Write it in a bottom-up manner (because the Python recursion stack is limited). Note that, assuming your subproblems from part (a) only find the size of the best result, you should also keep parent pointers so that you can reconstruct the actual subsequence.

code goes here:

#!/usr/bin/python def make_change(denominations, C): return 'NOT_IMPLEMENTED'

test using:

#!/usr/bin/python import unittest import sys import time import change class TestChange(unittest.TestCase): def test1_small(self): """small tests"""  self.change_test([1, 5, 10, 17], 0, 0) self.change_test([1, 5, 10, 17], 4, 4) self.change_test([1, 5, 10, 17], 5, 1) self.change_test([1, 5, 10, 17], 34, 2) self.change_test([1, 5, 10, 17], 33, 4) def test2_large(self): """large test"""  denominations = [1, 2896, 9274, 8063, 1764, 5375, 4228, 7611, 1482, 816, 9335, 2582, 4672, 649, 1405, 5362, 1790, 4774, 9978, 3175, 6091, 1302, 9683, 728, 9819, 1934, 863, 1828, 2680, 8911, 3065, 1010, 182, 2167, 4443, 7111, 493, 262, 5091, 3337, 3956, 3646, 244, 161, 9966, 7784, 3105, 7470, 2688, 1894, 4561, 9924, 557, 8192, 7142, 4046, 8344, 6368, 7391, 7459, 395, 2680, 5844, 376, 183, 7622, 537, 5526, 371, 4769, 4498, 4452, 2727, 3929, 600, 2633, 8090, 3829, 4186, 135, 1847, 9421, 9110, 3429, 2633, 1423, 78, 4059, 9877, 2749, 7422, 5200, 9310, 49, 3456, 9770, 7729, 7724, 1175, 7743, 8492] C = 100000 self.change_test(denominations, C, 11) def change_test(self, denominations, C, answer_size): coins = change.make_change(denominations, C) total = 0 for coin in coins: self.assertTrue(coin in denominations) total += coin self.assertEqual(C, total) self.assertEqual(answer_size, len(coins)) if __name__ == '__main__': unittest.main(argv = sys.argv + ['--verbose'])