Making Change Implementation? Using C++ language to implement your Dynamic Progr

Question

Making Change Implementation?

Using C++ language to implement your Dynamic Program change algorithm. The program should read input from a file named “amount.txt”. The file contains lists of denominations (V) followed on the next line by the amount A.

Example amount.txt:
1 2 5
10
1 3 7 12
29
1 2 4 8
15

In the above example the first line contains the denominations V=(1, 2, 5) and the next line contains the amount A = 10 for which we need change. There are three different denomination sets and amounts in the above example. A denomination set will be on a single line and will always start with the 1 “coin”. The results should be written to a file named change.txt and should contain the denomination set, the amount A, the change result array and the minimum number of coins used.

Example change.txt:
1 2 5
10
0 0 2
2
1 3 7 12
29
0 1 2 1
4
1 2 4 8
15
1 1 1 1
4

In the above example, to make 29 cents change from the denomination set (1, 3, 7, 12) you need 0: 1 cent coin, 1: 3 cent coin, 2: 7 cent coins and 1: 12 cent coin for a total of 4 coins.

Explanation / Answer

I have considered that the amount entered in amount.txt will never be 1. Based on this logic I have accepted the input.

CODE

#include <iostream>
#include <vector>
#include <map>
#include <stdio.h>

using namespace std;

void compute(vector<int> denominations) {

   //OutFile.
   FILE *fp = fopen("change.txt","a+");
  
   // Last element in vector is the amount;
   // taking the amount
   int amount = denominations[denominations.size()-1];
   // the last element is the amount hence removing it from denominations.
   denominations.pop_back();
   // A DP array of number of denominations by amount.
   std::vector<std::vector<int> > dp(
                denominations.size()+1,
                    std::vector<int>(amount+1, 0));
   // dp[i][j] is the minimum number of coins needed to make amount j having
   // only i coins.
  
   // MAP to hold the number of coins of a denominations.
   map<int,int> denomCount;
   for(int i = 0;i<(int)denominations.size();i++) {
       denomCount.insert(make_pair(denominations[i],0));
       //printing the denominations.
       fprintf(fp,"%d ",denominations[i]);
       //cout<<denominations[i]<<" ";
   }

   // printinng the amount
   fprintf(fp," %d ",amount);
   //cout<<endl<<amount<<endl;

   for(int i = 0; i <=(int)denominations.size(); i++) {
       // initializing the first column to all zeroes.
       dp[i][0] = 0;
   }
   for(int i = 0; i <=amount; i++) {
       // initializing the first row with max. used more than amount.
       dp[0][i] = amount+10;
   }

   // Iteratng over amount.
   for(int i = 1; i<=amount; i++) {
       // For each denomination
       for(int j = 1; j <= (int)denominations.size(); j++) {
           // if denomination is less than the amount
           if(denominations[j-1] <= i) {
               // take the minimum between considering the coin and not considering the coin.
               dp[j][i] = min(dp[j-1][i], dp[j][i-denominations[j-1]] + 1);
           }
           else {
               // else do not consider the coin.
               dp[j][i] = dp[j-1][i];
           }
       }
   }
  
   // FOR DEBUGGING PURPOSE

//   for(int i = 0; i<=(int)denominations.size(); i++) {
//       for(int j = 0; j <= amount; j++) {
//           cout<<dp[i][j]<<" ";
//       }
//       cout<<endl;
//   }

   int i = denominations.size();
   int j = amount;
   int min1 = dp[i][j];

   // find out the actual denominations used.
   while(j != 0) {
       // check if we have included that coin
       if(dp[i-1][j] == min1 )// not included go one row back
           i--;
       else {
           // coin is taken subtract the value and check again.
           denomCount[denominations[i-1]]++;
           j = j - denominations[i-1];
           min1= dp[i][j];
       }
   }
   // print the denomination count.
   for(int i = 0; i < (int)denomCount.size(); i++) {
       fprintf(fp,"%d ",denomCount[denominations[i]]);
       //cout<<denomCount[denominations[i]]<<" ";
   }
   // print the minimum coins.
   fprintf(fp," %d ",dp[denominations.size()][amount]);
   //cout<<endl<<dp[denominations.size()][amount]<<endl;
   fclose(fp);
}

int main() {

   int tmp;
   vector<int> denominations;

   FILE *fp = fopen("amount.txt","r"),*outFile = fopen("change.txt","w");
   fclose(outFile);
   fscanf(fp,"%d",&tmp);
   denominations.push_back(tmp);

   while(fscanf(fp,"%d",&tmp)!=EOF) {
       if(tmp == 1) {
           compute(denominations);
           denominations.clear();
       }
       denominations.push_back(tmp);
   }

   compute(denominations);

   return 0;
}

Sample output (change.txt)

1 2 5
10
0 0 2
2
1 3 7 12
29
0 1 2 1
4
1 2 4 8
15
1 1 1 1
4

Thanks

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.