Using C++ or Python 3

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.

//Java was used to make the algorithm. The greedy algorithm always provides a solution but doesnt guarantee the smallest number of coins used. The greedy algorithm takes ()nkO for any kind of coin set denomination, where k is the number of different coins in a particular set. /***Makes change using a recursive Greedyalgorithm. * @param amount: The amount of change to make. * *@paramcoins: The sorted set of coins,ordered from smallest to largest. * *@return: The number of coins used to make the change. * */ int makeChangeGreedyStyle(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 = coins[i - 1]; // If the next largest coin is found, print out its value. if (amount >= coin) { System.out.print(coin + " "); return 1 + makeChangeGreedyStyle(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; }