Question

You are implementing a brand new type of ATM that provides exact amounts of cash (bills only, no coins). In order to maximize potential revenue an algorithm is needed that will allow for using different denomination amounts as needed by the local currency (value of bills will vary, but are integers).

1. The program shall graphically prompt the user for a file.

2. The program shall read the selected file of which the first line will be a space separated list of the

   bill denomination sizes.

3. The program shall then read each line in the rest of the file containing an integer and output the

   number of different ways to produce that value using the denominations listed in the first line.

4. The program shall indicate after that the number of milliseconds the program spent calculating

   the answer.

5. The program shall implement 2 different forms of the algorithm: 1 recursive and 1 using dynamic

   programming.

6. The program shall have 2 sets of output, 1 for each implementation.

7. The program shall write the output to a file in the same directory as the input file.

8. The program must be written in Java.

Answer 1

import java.io.*;
import java.util.*;
class Main {

    public static int calculate_dp_bottomup_approach(int denominations[], int amount) {
        // Dynamic programming approach
        int dp[] = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i < denominations.length; i++)
            for (int j = denominations[i]; j <= amount; j++)
                dp[j] += dp[j - denominations[i]];
        return dp[amount];
    }

    public static int calculate_recursive(int denominations[], int index, int amount) {
        // recursive brute force approach
        if (amount == 0)
            return 1;
        if (amount < 0 || (index < 0 && amount >= 1))
            return 0;
        return calculate_recursive(denominations, index - 1, amount ) +
               calculate_recursive(denominations, index, amount - denominations[index] );
    }
    public static void main(String...args) throws Exception {
        System.out.println("Please enter file path");
        Scanner input = new Scanner(System.in);
        String path = input.next();
        File file = new File(path);
        while (!file.exists()) {
            System.out.println("File path entered is incorrect. Please specify correct path");
            System.out.println("Note enter file path in forward slash notation or use two back slash notation");
            file = new File(input.next());
        }
        Scanner readFile = new Scanner(file);
        PrintStream output = new PrintStream(new File(file.getParent() + "/output.txt"));
        System.setOut(output);
        String[] denominationsString = readFile.nextLine().split(" ");
        int []denominations = new int[denominationsString.length];
        for (int i = 0; i < denominationsString.length; i++)
            denominations[i] = Integer.parseInt(denominationsString[i]);
        long begin, end, duration1, duration2;
        int ans1 = 0, ans2 = 0;
        while (readFile.hasNext()) {
            int amount = readFile.nextInt();
            begin = System.currentTimeMillis();
            ans1 = calculate_recursive(denominations, denominations.length - 1, amount);
            end = System.currentTimeMillis();
            duration1 = end - begin;

            begin = System.currentTimeMillis();
            ans2 = calculate_dp_bottomup_approach(denominations, amount);
            end = System.currentTimeMillis();
            duration2 = end - begin;
            System.out.println("For amount " + amount);
            System.out.println("Using recursion number of ways is " + ans1 + " and time taken is " + duration1 + " ms");
            System.out.println("Using dynamic programming number of ways is " + ans2 + " and time taken is " + duration2 + " ms");
            System.out.println();
        }

    }
}

Sample Input:

path provided :  C:/folder1/folder2/input.txt

input.txt

2 3 4 5 6 7 8 9
1
4
5
6
7
8
100

output.txt

For amount 1
Using recursion number of ways is 0 and time taken is 0 ms
Using dynamic programming number of ways is 0 and time taken is 0 ms

For amount 4
Using recursion number of ways is 2 and time taken is 0 ms
Using dynamic programming number of ways is 2 and time taken is 0 ms

For amount 5
Using recursion number of ways is 2 and time taken is 0 ms
Using dynamic programming number of ways is 2 and time taken is 0 ms

For amount 6
Using recursion number of ways is 4 and time taken is 0 ms
Using dynamic programming number of ways is 4 and time taken is 0 ms

For amount 7
Using recursion number of ways is 4 and time taken is 0 ms
Using dynamic programming number of ways is 4 and time taken is 0 ms

For amount 8
Using recursion number of ways is 7 and time taken is 0 ms
Using dynamic programming number of ways is 7 and time taken is 0 ms

For amount 100
Using recursion number of ways is 212713 and time taken is 31 ms
Using dynamic programming number of ways is 212713 and time taken is 0 ms