ENGINEERING COLLEGE

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

Answer 1

Answer:

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

Related Questions

Water exiting the condenser of a power plant at 45 Centers a cooling tower with a mas flow rate of 15,000 kg/s. A stream of cooled water is returned to the condenser at the same flowrate. Makeup water is added in a separate stream at 20 C. Atmosphericair enters the cooling tower at 30 C, with a wet bulb temperature of 20 C. The volumetric flow rate of moist air into the cooling tower is 8000 m3/s. Moist air exits the tower at 40C and 90% RH. Assume atmospheric pressure is at 101.3 kPa. Determine: a.T
The 15-kg block A slides on the surface for which µk = 0.3. The block has a velocity v = 10 m/s when it is s = 4 m from the 10-kg block B. If the unstrectched spring has a stiffness k = 1000 N/m, determine the maximum compression of the spring due to the collision. Assume the collision is perfectly plastic. Take e=0.6 .
Cody’s car accelerates from 0m/s to 45 m/s northward in 15 seconds. What is the acceleration of the car
In contrasting the read-evaluation loop and the notification-based paradigm for inter- active programs, construction of a pre-emptive dialog was discussed. How would a programmer describe a pre-emptive dialog by purely graphical means? (Hint: Refer to the discussion in Sec- tion 8.5 concerning the shift from external and independent dialog management to presentation control of the dialog)
A 15. μF capacitor is connected to a 50. V battery and becomes fully charged. The battery is removed and a slab of dielectric that completely fills the space between the plates is inserted. If the dielectric has a dielectric constant of 5.0, what is the voltage across the capacitor's plates after the slab is inserted?

A hot brass plate is having its upper surface cooled by impinging jet of air at temperature of 15°C and convection heat transfer coefficient of 220 W/m^2•K. The 10-cm thick brass plate (rho = 8530 kg/m^3, cp = 380 J/kg•K, k = 110 W/m•K, and α = 33.9×10^–6 m^2/s) has a uniform initial temperature of 900°C, and the bottom surface of the plate is insulated. Required:
Determine the temperature at the center plane of the brass plate after 3 minutes of cooling.

Answers

Answer:

809.98°C

Explanation:

STEP ONE: The first step to take in order to solve this particular Question or problem is to find or determine the Biot value.

Biot value = (heat transfer coefficient × length) ÷ thermal conductivity.

Biot value = (220 × 0.1)÷ 110 = 0.2.

Biot value = 0.2.

STEP TWO: Determine the Fourier number. Since the Biot value is greater than 0.1. Tis can be done by making use of the formula below;

Fourier number = thermal diffusivity × time ÷ (length)^2.

Fourier number = (3 × 60 × 33.9 × 10^-6)/( 0.1)^2 = 0.6102.

STEP THREE: This is the last step for the question, here we will be calculating the temperature of the center plane of the brass plate after 3 minutes.

Thus, the temperature of the center plane of the brass plane after 3 minutes = (1.00705) (0.89199) (900- 15) + 15.

= > the temperature of the center plane of the brass plane after 3 minutes = 809.98°C.

Make a copy of the pthreads_skeleton.cpp program and name it pthreads_p2.cpp Modify the main function to implement a loop that reads 10 integers from the console (user input) and stores these numbers in a one-dimensional (1D) array (this code will go right after the comment that says ""Add code to perform any needed initialization or to process user input""). You should use a global array for this.

Answers

Answer:

The solution code is as follows:

#include <iostream>
using namespace std;
int main()
{
int myArray [10] = {};
int i;
for( i = 0; i < 10; i++ )
{
cout <<"Enter an integer: ";
cin>> myArray[i];
}
}

Explanation:

Firstly, we initialize a 10-elements array, myArray (Line 7) with no values.

Next, we create a for-loop (Line 10). Within the loop, we prompt user to enter an integer and assign the input value to the current element of myArray (Line 12-13).

An activated sludge plant is being designed to handle a feed rate of 0.438 m3 /sec. The influent BOD concentration is 150 mg/L and the cell concentration (MLVSS) is 2,200 mg/L. If you wish to operate the plant with a food-to-microorganism ratio of 0.20 day-1 , what volume of aeration tank should you use? Please give your answer in m3 .

Answers

Answer:

Volume of aeration tank = 1.29 x 10^4 m³

Explanation:

Food/Micro- organism Ratio = 0.2/day

Feed Rate (Q) = 0.438 m³/s

Influent BOD = 150 mg/L

MLVSS = 2200 mg/L

The above mentioned parameters are related by the equation

F/M = QS₀/VX

where S₀ is the influent BOD and X is the cell concentration, with V being the Volume of the tank. Re- arranging the above equation for V and putting the values in, we get

V = 0.4380 x 150/0.2 x 2200

V = 0.1493 (m³/s) x day

V = 0.1493 x 24 x 60 x 60

V = 1.29 x 10^4 m³

A cylindrical bar of metal having a diameter of 19.2 mm and a length of 207 mm is deformed elastically in tension with a force of 52900 N. Given that the elastic modulus and Poisson's ratio of the metal are 61.4 GPa and 0.34, respectively, determine the following: a. The amount by which this specimen will elongate in the direction of the applied stress.
b. The change in diameter of the specimen. Indicate an increase in diameter with a positive number and a decrease with a negative number.

Answers

Answer:

1)ΔL = 0.616 mm

2)Δd = 0.00194 mm

Explanation:

We are given;

Force; F = 52900 N

Initial length; L_o = 207 mm = 0.207 m

Diameter; d_o = 19.2 mm = 0.0192 m

Elastic modulus; E = 61.4 GPa = 61.4 × 10^(9) N/m²

Now, from Hooke's law;

E = σ/ε

Where; σ is stress = force/area = F/A

A = πd²/4 = π × 0.0192²/4

A = 0.00009216π

σ = 52900/0.00009216π

ε = ΔL/L_o

ε = ΔL/0.207

Thus,from E = σ/ε, we have;

61.4 × 10^(9) = (52900/0.00009216π) ÷ (ΔL/0.207)

Making ΔL the subject, we have;

ΔL = (52900 × 0.207)/(61.4 × 10^(9) × 0.00009216π)

ΔL = 0.616 × 10^(-3) m

ΔL = 0.616 mm

B) Poisson's ratio is given as;

υ = ε_x/ε_z

ε_x = Δd/d_o

ε_z = ΔL/L_o

Thus;

υ = (Δd/d_o) ÷ (ΔL/L_o)

Making Δd the subject gives;

Δd = (υ × d_o × ΔL)/L_o

We are given Poisson's ratio to be 0.34.

Thus;

Δd = (0.34 × 19.2 × 0.616)/207

Δd = 0.00194 mm

The 50mm diameter cylinder is made from Am 1004-T61 magnesium (E = 44.7GPa, a = 26x10^-6/°C)and is placed in the clamp when the temperature is T1 = 15°C. If the two 304-stainless-steel (E =
193GPa, a = 17x10^-6/°C) carriage bolts of the clamp each have a diameter of 10mm, and they hold
the cylinder snug with a negligible force against the rigid jaws, determine the temperature at which
the average normal stress in either the magnesium or steel becomes 12 MPa.

Answers

Answer:

......................

Explanation:

At full load, a commercially available 100hp, three phase induction motor operates at an efficiency of 97% and a power factor of 0.88 lag. The motor is supplied from a three-phase outlet with a line voltage rating of 208V.a. What is the magnitude of the line current drawn from the 208 V outlet? (1 hp = 746 W.) b. Calculate the reactive power supplied to the motor.