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 explained below

Step-by-step 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;

}