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