Engineering, 22.02.2020 04:14 natjon528

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

Answers: 1

Show answers

Answers

Answer from: kennyg02

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

Answer from: Quest

answer:

just reverse the digits.

: )

Answer from: Quest

answer:

c. the follow me tool

update this is wrong answer idk the answer

Another question on Engineering

Engineering, 03.07.2019 14:10

Amass of m 1.5 kg of steam is contained in a closed rigid container. initially the pressure and temperature of the steam are: p 1.5 mpa and t 240°c (superheated state), respectively. then the temperature drops to t2= 100°c as the result of heat transfer to the surroundings. determine: a) quality of the steam at the end of the process, b) heat transfer with the surroundings. for: p1.5 mpa and t 240°c: enthalpy of superheated vapour is 2900 kj/kg, specific volume of superheated vapour is 0. 1483 m/kg, while for t 100°c: enthalpy of saturated liquid water is 419kj/kg, specific volume of saturated liquid water is 0.001043m/kg, enthalpy of saturated vapour is 2676 kj/kg, specific volume of saturated vapour is 1.672 m/kg and pressure is 0.1 mpa.

Answers: 3

Answer

Engineering, 04.07.2019 18:10

The temperature of air decreases as it is compressed by an adiabatic compressor. a)- true b)- false

Answers: 2

Answer

Engineering, 04.07.2019 18:10

Apump is used to circulate hot water in a home heating system. water enters the well-insulated pump operating at steady state at a rate of 0.42 gal/min. the inlet pressure and temperature are 14.7 lbf/in.2, and 180°f, respectively; at the exit the pressure is 60 lbf/in.2 the pump requires 1/15 hp of power input. water can be modeled as an incompressible substance with constant density of 60.58 lb/ft3 and constant specific heat of 1 btu/lb or. neglecting kinetic and potential energy effects, determine the temperature change, in °r, as the water flows through the pump.

Answers: 1

Answer

Engineering, 04.07.2019 18:10

Courses that are developed by subject matter experts, internal or extemal to the college or university. these programs are marketed by the school (clo2) marks a)-vocational schools b)-vendor training c)-colleges & universities d)-continuing education programs

Answers: 2

Answer

You know the right answer?

IN JAVA,

Knapsack Problem

The file KnapsackData1.txt and KnapsackData2.txt a...

Questions