Question

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

Answer 1

Answer:

Answer explained below

Explanation:

Below is the code for Greedy change algorithm in C++. Please let me know what  does c ,k and represent in the question. so that i can update according to requirement

#include <bits/stdc++.h>  

using namespace std;  

int deno[] = { 1, 3,9,27,81 };  

int n = sizeof(deno) / sizeof(deno[0]);  

void findMin(int V)  

{  

   // Initialize result  

   vector<int> ans;  

   // Traverse through all denomination  

   for (int i = n - 1; i >= 0; i--) {  

       // Find denominations  

       while (V >= deno[i]) {  

           V -= deno[i];  

           ans.push_back(deno[i]);  

       }  

   }  

   // Print result  

   for (int i = 0; i < ans.size(); i++)  

       cout << ans[i] << " ";  

}  

int main()  

{  

   int n = 38;  

   cout << "Following is minimal number of change for " << n << ": ";  

   findMin(n);  

   return 0;  

}