contestada

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

Respuesta :

mirianmoses

Answer:

Explanation:

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