Question

IMPLEMENT IN JAVA PLEASE I NEED THIS DONE ASAP

Question 1 (25pt) Dynamic Programming – Coin Change

Design algorithm for the coin change problem using dynamic programming approach. Given coin denominations by value: c1 < c2 < … < cn, and change amount of x, find out how to pay amount x to customer using fewest number of coins.

Your algorithm needs to work for ANY coin denomination c1 < c2 < … < cn, and ANY change amount of x. For example, given coin denominations 1, 5, 10, 25, x=78, the solution is {3 coins of 25 and 3 coins of 1, total 6 coins}.

NEED TO DO ALL 3 PARTS

• Present your algorithm in pseudo code.

• Trace your algorithm and show how it works on a small example, show the step-by-step process and the final result.

• Analyze the time complexity of the algorithm and present the result using order notation.

Answer 1

As per your question, The pseudo code and java 8 program is written correctly and perfectly. Please have a look on the source code(please refer in-line comments for better understanding) and the run output below:-

COIN-CHANGE-MODIFIED(coins, coinsCount, toBeChangeValue)
  M[coinsCount+1]
  M[0] = 0

  S[coinsCount+1]
  S[0] = 0

  for j in 1 to coinsCount
    minimum = INF

    for i in 1 to toBeChangeValue
      if j >= coins[i]
        if 1+M[j-coins[i]] < minimum
          minimum = 1+M[j-coins[i]]
          coin = i

    M[j] = minimum
    S[j] = coin

  //Code to print the coins, given below
  ...
  return M[coinsCount]

=> The Java 8 program as per your question(please refer in-line comments for better understanding):-

import java.util.Scanner;

public class coin{

        //creating the scanner object
        private static Scanner scan = new Scanner(System.in);

        //the main driver method
        public static void main(String[] args){
                System.out.println("Enter the coins value(space separated): ");
                //taking space separated coins value from user
                String s[]= scan.nextLine().split(" ");

                //creating the coins integer array for holding coins value
                int coins[] = new int[s.length];

                //copying the coins value into the coins integer array from string array
                for(int i =0 ;i < s.length;i++){
                        coins[i]= Integer.parseInt(s[i]);
                }
                
                System.out.print("Enter the Value: ");
                //taking the x value that require to change 
                int xValue = scan.nextInt();

                System.out.println("At least " + coinChangeProblem(coins, xValue)
                + " coins are required to make a value of " + xValue + " from given coins");
        }
        /*
         * min method, compare and return min value
         * @param a - int
         * @param b - int
         * @returns min - int
         */
        public static int min(int a, int b){
                int min = (a <= b) ? a : b;
                return min;
        }
        /*
         * @param coins array
         * @param xValue - value for which need changes
         * @return the minimum no of coins required to change the xValue(sum)
         */
        public static int coinChangeProblem(int[] coins, int sum){ 

                //getting number of coins -> coins count
                int totalCoins = coins.length;

                // Creating array which stores subproblems' solutions
                int[][] arr = new int[totalCoins + 1][sum + 1];

                // Initialising first row with +ve infinity
                for(int j = 0; j <= sum; j++){
                        arr[0][j] = Integer.MAX_VALUE;
                }             

                // Initialising first column with 0
                for(int i = 1; i <= totalCoins; i++){
                        arr[i][0] = 0;
                }

                // Implementing the recursive solution
                for(int i = 1; i <= totalCoins; i++){
                        for(int j = 1; j <= sum; j++){
                                if(coins[i - 1] <= j)
                                        arr[i][j] = min(1 + arr[i][j - coins[i - 1]], arr[i - 1][j]);
                                else
                                        arr[i][j] = arr[i - 1][j];
                        }
                }
                //returning the needed minimum no of coins 
                return (int)arr[totalCoins][sum];
        }
}

=> The Run output(as per your example):-

I hope, now you have crestal and clear undersatnding of Coin Change Problem and Its Dynamic Programming Solution.

Please don't forget to like it...

Thank You...