Using C++, C or Python

This part is completed -> used to provide background

Consider the problem of making change for n cents using the fewest number of coins. Assume that each coins value is an integer.

Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are c0, c1, , ck for some integers c > 1 and k 1. Show that the greedy algorithm of picking the largest denomation first always yields an optimal solution. You are expected to reason about why this approach gives an optimal solution. (Hint: Show that for each denomination ci, the optimal solution must have less than c coins.)

Design an O(nk) time algorithm that makes change for any set of k different coin denominaions, assuming that one of the coins is a penny.

Algorithm built using java /***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; }

Problem:

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.