Implement the make change algorithm..
Please program in PYTHON
Please use GREEDY approach
Please provide COMMENTS and OUTPUT
Use PSEUDOCODE provided below for template
Please FORMAT OUTPUT CORRECTLY
Problem 4. (7 points) Implementation: Implement the make change algorithm you designed in the previous problem. Your program should read a text file "data.txt" where each line in "data.txt" contains three values c, k and n. Please make sure you take your input in the specified order c, k and n. For example, a line in "data.txt" may look like the following: 3 4 38 where c= 3, k = 4, n = 38. That is, the set of denominations is {30, 31, 32, 33, 34} = {1,3,9, 27,81}, and we would like to make change for n = 38. The file "data.txt" may include multiple lines like above. The output will be written to a file called "change.txt", where the output corresponding to each input line contains a few lines. Each line has two numbers, where the first number denotes a de- nomination and the second number represents the cardinality of that denomination in the solution. For example, for the above input line '3 4 38', the optimal solution is the multiset {27,9,1,1), and the output in the file "change.txt" is as follows: 27 1 91 12 which means the solution contains 1 coin of denomination 27, one coin of 9 and two coins of denomination 1. You can use a delimiter line to separate the outputs generated for different input lines. Makes change using a recursive Greedy algorithm. @param amount The amount of change to make. @param coins The sorted set of coins, ordered from smallest to largest. * @return The number of coins used to make the change. int makeChangeGreedy Style (int amount, int[] coins) { // Check if there is no more change to make. if (amount == 0) { System.out.println(""); return 0; // Loop over the change in order of greatest to smallest. for (int i = coins.length; i > 0; i--) { int coin = coinsi - 1]; // If the next largest coin is found, print out its value. if (amount >= coin) { System.out.print(coin + " "); return 1 + make change GreedyStyle(amount - coin, coins); // Arriving here means it's impossible to make change // using this greedy algorithm, this amount of change, // and this set of coins. System.out.print("Cannot make change; "); System.out.println("cents remaining: " + amount); return 0; Problem 4. (7 points) Implementation: Implement the make change algorithm you designed in the previous problem. Your program should read a text file "data.txt" where each line in "data.txt" contains three values c, k and n. Please make sure you take your input in the specified order c, k and n. For example, a line in "data.txt" may look like the following: 3 4 38 where c= 3, k = 4, n = 38. That is, the set of denominations is {30, 31, 32, 33, 34} = {1,3,9, 27,81}, and we would like to make change for n = 38. The file "data.txt" may include multiple lines like above. The output will be written to a file called "change.txt", where the output corresponding to each input line contains a few lines. Each line has two numbers, where the first number denotes a de- nomination and the second number represents the cardinality of that denomination in the solution. For example, for the above input line '3 4 38', the optimal solution is the multiset {27,9,1,1), and the output in the file "change.txt" is as follows: 27 1 91 12 which means the solution contains 1 coin of denomination 27, one coin of 9 and two coins of denomination 1. You can use a delimiter line to separate the outputs generated for different input lines. Makes change using a recursive Greedy algorithm. @param amount The amount of change to make. @param coins The sorted set of coins, ordered from smallest to largest. * @return The number of coins used to make the change. int makeChangeGreedy Style (int amount, int[] coins) { // Check if there is no more change to make. if (amount == 0) { System.out.println(""); return 0; // Loop over the change in order of greatest to smallest. for (int i = coins.length; i > 0; i--) { int coin = coinsi - 1]; // If the next largest coin is found, print out its value. if (amount >= coin) { System.out.print(coin + " "); return 1 + make change GreedyStyle(amount - coin, coins); // Arriving here means it's impossible to make change // using this greedy algorithm, this amount of change, // and this set of coins. System.out.print("Cannot make change; "); System.out.println("cents remaining: " + amount); return 0
