C++ Code to implement algorithm

#include

#include

#include

#include // for string tokenizer and c-style string processing

using namespace std;

int main(){

string coinInfoFilename;

cout

cin >> coinInfoFilename;

int numCoinValues;

cout

cin >> numCoinValues;

int TargetSumValue;

cout

cin >> TargetSumValue;

int* CoinValues = new int[numCoinValues+1]; // the + 1 is to account for coin index 0 with a value of $0

int* MinNumCoins = new int[TargetSumValue+1]; // the + 1 is to account for index 0 with a value of $0

int* LastCoinPicked = new int[TargetSumValue+1]; // the + 1 is to account for index 0 with an invalid value of -1

CoinValues[0] = 0;

MinNumCoins[0] = 0;

LastCoinPicked[0] = -1;

ifstream coinInfoFileReader(coinInfoFilename);

if (!coinInfoFileReader){

cout

return 0;

}

int numCharsPerLine = 25;

char *line = new char[numCharsPerLine];

// '25' is the maximum number of characters per line

coinInfoFileReader.getline(line, numCharsPerLine, ' ');

// ' ' is the delimiting character to stop reading the line

while (coinInfoFileReader){

char* cptr = strtok(line, " \t");

string coinIndexToken(cptr);

int coinIndex = stoi(coinIndexToken);

cptr = strtok(NULL, " \t");

string coinValueToken(cptr);

int coinValue = stoi(coinValueToken);

CoinValues[coinIndex] = coinValue;

coinInfoFileReader.getline(line, numCharsPerLine, ' ');

}

// Implement the algorithm here and the print the output as shown in the sample screenshot

return 0;

}

In this project, you will implement the dynamic programming-based solution for the coin change problem. You are given an array (CD) of N coins (for simplicity, coin index of 0 corresponds to a coin of $0; the valid coin indexes are 1...N) each with a unique positive integer value and a target value (S) for the sum of the coin values picked. You will input the array as a text file (format, as shown in the sample screenshot below) and the target sum value as an integer input. You are given a startup code (in C++/Java) that inputs the coin values from a text file and the target sum value. The code also initializes the three arrays for respectively storing the coin values, the minimum number of coins (MNC) picked for each value of the target sum in the range 1...S, and the last coin value picked (LCP) for the target sum in the range of 1...S You would extend the given code to implement the dynamic programming algorithm and print the output (the target sum values from 1...S and the contents of the two arrays MNC and LCP for each target sunm value) as shown in the sample screenshot. You are also required to print the coins to be picked for the targeted sum S (as shown in the sample screenshot) Sample screenshot Enter filename coinInfo.txt Enter the number of COin vaIues Enter the target sum of the coin values 1 Sun MNC LCP Coins to be picked for targeted sun 1? 2 5 5 5 1 2 3 4 5 67 8 9 10 11 12 13 14 15 16 17 1 1 2 1 1 2 22 2 2 33 3 3 3 4 4 1 2 2 4 5 1 2 4 4 5 1 2 44 5 1 2 4 4 coinInfo.txt Values assigned