import java.util.*;

import java.io.*;

class CoinChange{

public static void main(String[] args){

try{

Scanner input = new Scanner(System.in);

String filename;

System.out.print("Enter filename: ");

filename = input.next();

int numCoinValues;

System.out.print("Enter the number of coin values: ");

numCoinValues = input.nextInt();

int TargetSumValue;

System.out.print("Enter the target sum of the coin values: ");

TargetSumValue = input.nextInt();

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

FileReader fr = new FileReader(filename);

BufferedReader br = new BufferedReader(fr);

String line = null;

CoinValues[0] = 0;

MinNumCoins[0] = 0;

LastCoinPicked[0] = -1;

while ( (line = br.readLine() ) != null){

StringTokenizer stk = new StringTokenizer(line, " \t");

int coinIndex = Integer.parseInt(stk.nextToken());

CoinValues[coinIndex] = Integer.parseInt(stk.nextToken());

}

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

}

catch(Exception e){e.printStackTrace();}

}

}

Due: November 8, 2018: by 11.30 AM (in Canvas) 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 sum 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 values: 4 Enter the target sum of the coin values: 17 Sum MNC LCP Coins to be picked for targeted sum 1? 2 55 5 2 4 1 2 3 4567 8 9 10 11 12 13 14 15 16 17 1 1 2 1 1 2 2 2 2 2 3 3 3 3 3 4 4 1 2 2 4 5 1 2 4 4 5 1 2 4 4 5 1 2 4 coinInfo.txt Values assigned Coin DenominationSum of the Array (CD) 1 4 56 Coin Values (S) 20 Due: November 8, 2018: by 11.30 AM (in Canvas) 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 sum 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 values: 4 Enter the target sum of the coin values: 17 Sum MNC LCP Coins to be picked for targeted sum 1? 2 55 5 2 4 1 2 3 4567 8 9 10 11 12 13 14 15 16 17 1 1 2 1 1 2 2 2 2 2 3 3 3 3 3 4 4 1 2 2 4 5 1 2 4 4 5 1 2 4 4 5 1 2 4 coinInfo.txt Values assigned Coin DenominationSum of the Array (CD) 1 4 56 Coin Values (S) 20