In Python

1) The change-making algorithm is a well studied greedy algorithm. It is a subset of the Integer Knapsack problem, which is one of the most difficult and highly studied problems in computer science. The algorithm attempts to identify the minimum coinage needed to make change out of an input amount. Using the U.S. currency system (1,5,10,25), we would make change of 40 with one 25 coin, one 10 coin, and one 5 coin. The algorithm works by checking to see if the largest coin can be subtracted from the total without going negative. If so, it adds that coin and subtracts its value. This check is repeated until the total reaches 0, or subtracting the value of the largest coin causes it to go negative. Then it tries with the second largest coin. The process repeats until the total reaches 0. For most monetary systems, the greedy change-making algorithm will correctly produce results, but it is not guaranteed. Consider a system with coins of 1, 4, and 5. To make the greedy change-making algorithm will first take a 5 coin, realize it cannot take a 5 or a 4 coin, and add three 1 coins. The optimal solution uses two 4 coins. For this problem, you will implement two instances of monetary systems that do not always return optimal results. Your coinage system must contain at least four coins, which are each separated by at least 4 in value. Your system must include a 1 coin. Written: In the document, provide pseudocode for your solution, and analyze the runtime. What is the overall runtime dependent on? Provide proof that your monetary system will not work optimally with the greedy algorithm (i.e. show via counterexample that it does not always produce the minimal amount of change). Code: Implement the two instances inside the empty function blocks change_one and change_two. Note you will need to specify what the input parameters are, and what the return value should be. Test your method inside the main with two solutions that are correct (return the correct minimal change) and two that are not 1) The change-making algorithm is a well studied greedy algorithm. It is a subset of the Integer Knapsack problem, which is one of the most difficult and highly studied problems in computer science. The algorithm attempts to identify the minimum coinage needed to make change out of an input amount. Using the U.S. currency system (1,5,10,25), we would make change of 40 with one 25 coin, one 10 coin, and one 5 coin. The algorithm works by checking to see if the largest coin can be subtracted from the total without going negative. If so, it adds that coin and subtracts its value. This check is repeated until the total reaches 0, or subtracting the value of the largest coin causes it to go negative. Then it tries with the second largest coin. The process repeats until the total reaches 0. For most monetary systems, the greedy change-making algorithm will correctly produce results, but it is not guaranteed. Consider a system with coins of 1, 4, and 5. To make the greedy change-making algorithm will first take a 5 coin, realize it cannot take a 5 or a 4 coin, and add three 1 coins. The optimal solution uses two 4 coins. For this problem, you will implement two instances of monetary systems that do not always return optimal results. Your coinage system must contain at least four coins, which are each separated by at least 4 in value. Your system must include a 1 coin. Written: In the document, provide pseudocode for your solution, and analyze the runtime. What is the overall runtime dependent on? Provide proof that your monetary system will not work optimally with the greedy algorithm (i.e. show via counterexample that it does not always produce the minimal amount of change). Code: Implement the two instances inside the empty function blocks change_one and change_two. Note you will need to specify what the input parameters are, and what the return value should be. Test your method inside the main with two solutions that are correct (return the correct minimal change) and two that are not