Contest planning for highest score in JAVA Knapsack in JAVA!! INPUT and OUTPUT f

Question

Contest planning for highest score in JAVA

Knapsack in JAVA!!

INPUT and OUTPUT files

ContestA.in

4
10
2 4
3 5
4 6
6 7

ContestA.output

contestA.in has 4 problems over 10 hours
Pr#   Time   Points
1   2   4
2   3   5
3   4   6
4   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

ContestB.in

6
12
2 5
3 6
2 4
5 3
1 1
7 8

ContestB.output

contestB.in has 6 problems over 12 hours
Pr#   Time   Points
1   2   5
2   3   6
3   2   4
4   5   3
5   1   1
6   7   8

The selected problems for the highest contest score are:
   Problem   Points
   1   5
   2   6
   6   8

Target problem list yields 19 points

ContestC.in

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

ContestC.output

contestC.in has 7 problems over 10 hours
Pr#   Time   Points
1   4   3
2   2   4
3   5   9
4   1   1
5   3   3
6   7   8
7   6   7

The selected problems for the highest contest score are:
   Problem   Points
   2   4
   3   9
   5   3

Target problem list yields 16 points

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 Number of problems 10 2 3 umber of hours Hours & points per problem per prob- lem, repeating for up to 10 problems Table 1: Input file data layout 2.1 Functions Input Read input file passed as the first command line argument with one line each for the following: Number of problems an integer between 1 and 10 'The data in the file will be in the order shown above, tat is, problems, # contest hours, and up to 10 occurences of the problem time and problem points.

Explanation / Answer

import java.io.*;

import java.util.*;

public class Knapsack {

public static void main(String[] args)

{

File file = new File(args[0]);

int n = 0,h = 0;

int t[]=null;

int v[] = null;

try

{

Scanner sc = new Scanner(file);

n = sc.nextInt();

h = sc.nextInt();

t = new int[n+1];

v = new int[n+1];

t[0]=0;

v[0]=0;

for(int i=1;i<=n;i++)

{

t[i] = sc.nextInt();

v[i] = sc.nextInt();

}

sc.close();

}

catch (FileNotFoundException e)

{

e.printStackTrace();

}

System.out.println(args[0]+" has "+n+" problems over "+h+" hours");

System.out.println("Pr# Time Points");

for(int i=1;i<=n;i++)

{

System.out.println(i+" "+t[i]+" "+v[i]);

}

int dp[][] = new int[n+1][h+1];

//int ans[][][] = new int[n+1][h+1][n+1][2];

for(int i=0;i<=h;i++)

{

dp[0][i] = 0;

//ans[0][i][0] = 0;

}

for(int i=0;i<=n;i++)

{

dp[i][0] = 0;

//ans[i][0][0] = 0;

}

for(int i=1;i<=n;i++)

{

for(int j=1;j<=h;j++)

{

//ans[i][j]

dp[i][j] = dp[i-1][j];

if(j>=t[i])

{

if(dp[i-1][j-t[i]]+v[i] > dp[i][j])

{

dp[i][j] = dp[i-1][j-t[i]]+v[i];

//ans[i] = 1;

}

}

}

}

//System.out.println(h);

//System.out.println(dp[n][h]);

int tt = h;

int ans[] = new int[n+1];

for(int i=n;i>=1;i--)

{

ans[i]=0;

if(dp[i][tt]-dp[i-1][tt-t[i]]==v[i])

{

tt = tt - t[i];

ans[i]=1;

}

}

System.out.println("The selected problems for the highest contest score are: ");

System.out.println("Problem Points");

for(int i=1;i<=n;i++)

{

if(ans[i]==1)

{

System.out.println(i+" "+v[i]);

}

}

System.out.println("Target problem list yields "+dp[n][h]+" points");

}

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.