Question

1 Objective The rules for a new type of programming contest provides a list of problems, their respective score in integer points, and a statistically valid estimate of the time it takes to solve the problem. This duration or time is expressed in integer hours. To help with a solution strategy the contest organizers reveal there is a dynamic programming solution enabling all the contestants to maximize their score - and stay within the time limits for the contest. One of the rules' drawback is that the duration of the contest and the problem data is not announced until just before the contest start. Another drawback is that once a problem has been started it must be finished within the timeframe, otherwise there is no score credit for the problem being attempted. There is no penalty for finishing early and there is no benefit either, as the time gained cannot be applied to another problem. It is, however, acceptable to continue on to the next problem in the solution list generated from the dynamic program. The assignment is to build the dynamic program that creates the optimum problem list for the given number of problems and timeframe. 2 Requirements Read the input file formatted as follows. The input file will contain the following data, in the order shown below. Input Data Description 5 Number of contest problems 10 Number of contest hours 2 3 Hours per problem & points per prob- lem per problem, repeating for up to 10 problems Table 1: Input file data layout 2.1 Functions Input Read input file 1. passed as the first command line argument with one line each for the following: The data in the file will be in the order shown above, that is, #contest problems, #contest hours, and up to 10 occurences of the problem time and problem points. • Number of contest problems - an integer between 1 and 10 • Number of contest hours - an integer between 1 and 12 • Number of hours for the problem following by the number of points for this problem. For example: 4 10 would be a four hour problem worth ten points. These number pairs can occur up to 10 times. Schedule This function will determine the problem set to be attempted to maximize the contest score. Print list This function will print the optimum problem set as determined by the Schedule function described above. Additional methods and properties may be required to successfully implement the functions specified above. 3 Testing Make sure to test your code on Eustis even if it works perfectly on your machine. If your code does not compile on Eustis you will receive a 0 for the assignment. There will be three (3) input files and three (3) output files provided for testing your code, shown below in Outputs. Filename Description contest A.in 4 problems over 10 hours contest.B.in 6 problems over 12 hours contestC.in 7 problems over 10 hours Table 2: Input files The expected output for these test cases will also be provided as defined in Table L To compare your output to the expected output you will first need to redirect STDOUT to a text file. Run your code with the following command (substitute the actual names of the input and output file appropriately): java Hw03 inputFile > output.txt The run the following command (substitute the actual name of the expected output file): diff output.txt expectedOutputFile If there are any differences the relevant lines will be displayed (note that even a single extra space will cause a difference to be detected). If nothing is displayed, then congratulations the outputs match! For each of the three (3) test cases, your code will need to output to STDOUT text that is identical to the corresponding erpectedOutput File. If your code crashes for a particular test case, you will not get credit for that case. Please note that grading will be based on the input and output files described above, along with one or two other input files. The output files are shown in the table: Filename contest A output contest B.output contestC.output Table 3: Output file example As an example, contestA.output should look as follows: contestA. in has 4 problems over 10 hours Pr# Time Points 1 24 2 3 5 346 4 6 7 The selected problems for the highest contest score are: Problem Points 14 25 36 Target problem list yields 15 points 5 Sample output ff210377@eustis: "/COP3503$ java Hw03 contesta.in contestA. in has 4 problems over 10 hours Pr# Time Points 2 3 4 3 4 6 5 6 7 The selected problems for the highest contest score are: Problem Points 1 4 2 5 3 6 Target problem list yields 15 points ff210377@eustis:-/COP3503$ java Hw03 >contestB.testOut ff210377@eustis: "/COP3503$ diff contestB.testout contestB.output ff2103770eustis: "/COP3503$ Assume the columnar data for the problem detail data shown above is separated by the tab character ("\t"). This will minimize troubleshooting data alignment in the diff processing. Command Output filenames java Hw03 contest.A.in contest A.output java Hw03 contest B.in contest B.output java Hw03 contestC.in contestC.output Table 4: Commands with input files and corresponding output files.

Answer 1

program code to copy

DPOptimization.java

import java.io.File;
import java.util.Scanner;
import java.util.ArrayList;

public class DPOptimization 
{

    public static void main(String[] args) 
        {
        
        // Terminal Input Setup
        if (args.length > 0) 
                {
            File fileName = new File(args[0]);
            int numHrs = 0; int numProbs = 0;
            ArrayList<Integer> hrs = new ArrayList<Integer>();
            ArrayList<Integer> pts = new ArrayList<Integer>();

            // Process input
            readFile(fileName, numHrs, numProbs, hrs, pts);
           
        } 
                else 
                {
            System.err.println("Input file not specified!, try again");
        }
        
    }
    
    // READS INPUT FILE AND EXECUTES COMMANDS //
    public static void readFile(File fileName, int numHrs, int numProbs, ArrayList<Integer> hrs, ArrayList<Integer> pts) 
        {
        
        try 
                {
            int k; int counter = 1;
            String line;
            Scanner scan = new Scanner(fileName);
                      
            // Get # of problems and # of hours from input file
            line = scan.nextLine();
            numProbs = Integer.parseInt(line);
            line = scan.nextLine();
            numHrs = Integer.parseInt(line);
            System.out.println(fileName + " has " + numProbs + " problems over " + numHrs + " hours");
            System.out.println("Pr#\tTime\tPoints");
            
            // Read the rest of the lines in file
            while (scan.hasNextLine()) 
                        {
                line = scan.nextLine();
                String[] command = line.split(" ");
                if (command.length > 0) 
                                {
                    System.out.println(counter + "\t" + command[0] + "\t" + command[2]); 
                    hrs.add(Integer.parseInt(command[0]));
                    pts.add(Integer.parseInt(command[2]));
                    counter++;
                }
            }
            
            // Execute DP process
            k = genTable(numProbs, numHrs, hrs, pts);

        } 
                catch (Exception e) 
                {
            e.printStackTrace();
        }
    }
    
    // HELPER MAX FUNCTION //
    public static int findMax(int a, int b) 
        {
        if (a > b) 
                {
            return a;
        }
        return b;
    }
        
    // SCHEDULE LOGIC //
    //---------------//

    // DP SOLUTION // 0-1 Knapsack Problem
    public static int genTable(int numPrbs, int numHrs, ArrayList<Integer> hrs, ArrayList<Integer> pts) 
        {
        // Serves as the DP table
        int[][] k = new int[numPrbs + 1][numHrs + 1];
        
        // Knapsask
        int sack[] = new int[numPrbs];

         // Building DP table from the bottom up
        for (int i = 0; i <= numPrbs; i++) 
                {
            for (int w = 0; w <= numHrs; w++) 
                        {

                // Base Case - Initialization
                if (i == 0 || w == 0) 
                                {
                    k[i][w] = 0;

                // Current problem does not exceed max hours 
                } 
                                else if (hrs.get(i-1) <= w) 
                                {     
                    k[i][w] = findMax(pts.get(i-1) + k[i-1][w - hrs.get(i-1)], k[i-1][w]);
                    
                } 
                                else 
                                {
                    k[i][w] = k[i-1][w];
                        
                }
            }
        }


        // Traverse back and collect items in knapsack
        int temp1 = numPrbs; int temp2 = numHrs; int sackIndex = 0;
        while (numPrbs > 0) 
                {

            // Detects when it should account for a problem in the sack
            if (k[numPrbs][numHrs] != k[numPrbs-1][numHrs]) {
                sack[sackIndex] = numPrbs;  
                sackIndex++; numPrbs--;  
                numHrs = numHrs - hrs.get(numPrbs);
            } else {
                numPrbs--;
            }
        }


        // Output optimal items
        System.out.println("\nThe selected  problems for the highest contest score are: ");
        System.out.println("\tProblem\tPoints");
        for (int x = sackIndex - 1; x >= 0; x--) 
                {
            System.out.println("\t" + sack[x] + "\t" + pts.get((int)sack[x]-1));
        }
        System.out.println("\nTarget problem list yields " + k[temp1][temp2] + " points");
        
        return k[temp1][temp2];

    }

}
===================================================================

contestA.in

4
10
2  4
3  5
4  6
6  7

sample output

Problems @ Javadoc B. Declaration Console X <terminated stock_Q6 [Java Application] C:\Program Files\Java\jrel.8.0_201\bin\javaw.exe (Aug 1, 2020, 12:39:40 AM) contesta.in has 4 problems over 10 hours Points Pr# 1 2 3 4 Time 2 3 4 6 4 5 6 7 The selected problems for the highest contest score are: Problem Points 1 2 3 4 5 6 Target problem list yields 15 points