Question

IN JAVA,

Knapsack Problem

The file KnapsackData1.txt and KnapsackData2.txt are sample input files

for the following Knapsack Problem that you will solve.

KnapsackData1.txt contains a list of four prospective projects for the upcoming year for a particular

company:

Project0 6 30

Project1 3 14

Project2 4 16

Project3 2 9

Each line in the file provides three pieces of information:

1) String: The name of the project;

2) Integer: The amount of employee labor that will be demanded by the project, measured in work weeks;

3) Integer: The net profit that the company can expect from engaging in the project, measured in thousands

of dollars.

Your task is to write a program that:

1) Prompts the user for the number of work weeks available (integer);

2) Prompts the user for the name of the input file (string);

3) Prompts the user for the name of the output file (string);

4) Reads the available projects from the input file;

5) Dolves the corresponding knapsack problem, without repetition of items; and

6) Writes to the output file a summary of the results, including the expected profit and a list of the best

projects for the company to undertake.

Here is a sample session with the program:

Enter the number of available employee work weeks: 10

Enter the name of input file: KnapsackData1.txt

Enter the name of output file: Output1.txt

Number of projects = 4

Done

For the above example, here is the output that should be written to Output1.txt:

Number of projects available: 4

Available employee work weeks: 10

Number of projects chosen: 2

Number of projectsTotal profit: 46

Project0 6 30

Project2 4 16

The file KnapsackData2.txt, contains one thousand prospective projects. Your program should also be able to handle this larger problem as well. The corresponding output file,

WardOutput2.txt, is below.

With a thousand prospective projects to consider, it will be impossible for your program to finish in a

reasonable amount of time if it uses a “brute-force search” that explicitly considers every possible

combination of projects. You are required to use a dynamic programming approach to this problem.

WardOutput2.txt:

Number of projects available: 1000

Available employee work weeks: 100

Number of projects chosen: 66

Total profit: 16096

Project15 2 236

Project73 3 397

Project90 2 302

Project114 1 139

Project117 1 158

Project153 3 354

Project161 2 344

Project181 1 140

Project211 1 191

Project213 2 268

Project214 2 386

Project254 1 170

Project257 4 427

Project274 1 148

Project275 1 212

Project281 2 414

Project290 1 215

Project306 2 455

Project334 3 339

Project346 2 215

Project356 3 337

Project363 1 159

Project377 1 105

Project389 1 142

Project397 1 321

Project399 1 351

Project407 3 340

Project414 1 266

Project431 1 114

Project435 3 382

Project446 1 139

Project452 1 127

Project456 1 229

Project461 1 319

Project478 1 158

Project482 2 273

Project492 1 142

Project525 1 144

Project531 1 382

Project574 1 170

Project594 1 125

Project636 2 345

Project644 1 169

Project668 1 191

Project676 1 117

Project684 1 143

Project689 1 108

Project690 1 216

Project713 1 367

Project724 1 127

Project729 2 239

Project738 1 252

Project779 1 115

Project791 1 110

Project818 2 434

Project820 1 222

Project830 1 179

Project888 3 381

Project934 3 461

Project939 3 358

Project951 1 165

Project959 2 351

Project962 1 316

Project967 1 191

Project984 1 117

Project997 1 187

Answer 1

Code:

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;

public class Knapsack {
  
   public static void knapsack(int wk[], int pr[], int W, String ofile) throws IOException
   {
       int i, w;
       int[][] Ksack = new int[wk.length + 1][W + 1];
      
       for (i = 0; i <= wk.length; i++) {
   for (w = 0; w <= W; w++) {
   if (i == 0 || w == 0)
   Ksack[i][w] = 0;
   else if (wk[i - 1] <= w)
   Ksack[i][w] = Math.max(pr[i - 1] + Ksack[i - 1][w - wk[i - 1]], Ksack[i - 1][w]);
   else
   Ksack[i][w] = Ksack[i - 1][w];
   }
   }
      
       int maxProfit = Ksack[wk.length][W];
       int tempProfit = maxProfit;
       int count = 0;
       w = W;
       int[] projectIncluded = new int[1000];
       for (i = wk.length; i > 0 && tempProfit > 0; i--) {
          
       if (tempProfit == Ksack[i - 1][w])
       continue;   
       else {
           projectIncluded[count++] = i-1;
       tempProfit = tempProfit - pr[i - 1];
       w = w - wk[i - 1];
       }
      
       FileWriter f =new FileWriter("C:\\Users\\gshubhita\\Desktop\\"+ ofile);
       f.write("Number of projects available: "+ wk.length+ "\r\n");
       f.write("Available employee work weeks: "+ W + "\r\n");
       f.write("Number of projects chosen: "+ count + "\r\n");
       f.write("Total profit: "+ maxProfit + "\r\n");
      
   for (int j = 0; j < count; j++)
   f.write("\nProject"+ projectIncluded[j] +" " +wk[projectIncluded[j]]+ " "+ pr[projectIncluded[j]] + "\r\n");
   f.close();
       }   
   }
  
   public static void main(String[] args) throws Exception
   {
       Scanner sc = new Scanner(System.in);
       System.out.print("Enter the number of available employee work weeks: ");
       int avbWeeks = sc.nextInt();
       System.out.print("Enter the name of input file: ");
   String inputFile = sc.next();
       System.out.print("Enter the name of output file: ");
       String outputFile = sc.next();
       System.out.print("Number of projects = ");
       int projects = sc.nextInt();

       int[] workWeeks = new int[projects];
       int[] profit = new int[projects];
      
       File file = new File("C:\\Users\\gshubhita\\Desktop\\" + inputFile);
   Scanner fl = new Scanner(file);
  
   int count = 0;
   while (fl.hasNextLine()){
   String line = fl.nextLine();
   String[] x = line.split(" ");
   workWeeks[count] = Integer.parseInt(x[1]);
   profit[count] = Integer.parseInt(x[2]);
   count++;
   }
  
   knapsack(workWeeks, profit, avbWeeks, outputFile);
   }

}

Console Output:

Enter the number of available employee work weeks: 10
Enter the name of input file: input.txt
Enter the name of output file: output.txt
Number of projects = 4

Output.txt:

Number of projects available: 4
Available employee work weeks: 10
Number of projects chosen: 2
Total profit: 46

Project2 4 16

Project0 6 30