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
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
IN JAVA, Knapsack Problem The file KnapsackData1.txt and KnapsackData2.txt are sample input files...
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...
JAVA - Natural Quick Sort .txt and Return ----------------------------------------------------------------------------- The program should input a .txt file like below and must use a Quick sort Algorithm ================ 6 10 4 19 10 12 8 6 0 1 2 3 ================ The first number "6" represents the index of the element to return after sort the second number on the top "10" represents the number of elements or size of array. The following numbers and lines are the elements that need to...
There is a file called mat2.txt in our files area under the Assignments folder. Download it and save it in the same folder where this Matlab file (HW08_02.m) is saved. It may be worth opening that text file to see how it is set out. Note well, however, that the file might have a different number of lines and different number of numbers on each line. Write a Matlab program that does the following: Prompt the user for an input...
Consider an input file A2.txt. Each line of A2.txt consists of two numbers separated by space. Write a C++ program that reads the two numbers from each line and prints how many numbers are prime between them. Your program must have a user defined function that takes one number as input parameter and detects whether its prime or not. Show your output in a file named B2.txt using the following format: Sample Input: 3 17 42 91 Sample Output: 6...
Please write this in C. Write this code in Visual Studio and upload your Source.cpp file for checking (1) Write a program to prompt the user for an output file name and 2 input file names. The program should check for errors in opening the files, and print the name of any file which has an error, and exit if an error occurs opening any of the 3 For example, (user input shown in caps in first line) Enter first...
Objective: Use input/output files, strings, and command line arguments. Write a program that processes a text file by removing all blank lines (including lines that only contain white spaces), all spaces/tabs before the beginning of the line, and all spaces/tabs at the end of the line. The file must be saved under a different name with all the lines numbered and a single blank line added at the end of the file. For example, if the input file is given...
Consider an input file A1.txt. Each line of A1.txt consists of two numbers separated by space. Write a C++ program that reads the two numbers from each line and adds all the integers between those two numbers (starting from the first number and ending at the second. Show your output in B1.txt. Sample Input: 1 6 18 74 29 38 Sample Output: 21 2622 335 (For further clarification, the first line of the sample output was done by 1+2+3+4+5+6 =...
4.3Learning Objective: To read and write text files. Instructions: This is complete program with one Java source code file named H01_43.java (your main class is named H01_43). Problem: Write a program that prompts the user for the name of a Java source code file (you may assume the file contains Java source code and has a .java filename extension; we will not test your program on non-Java source code files). The program shall read the source code file and output...
JAVA 6. Create two files and name them: puzzle.txt and puzzle2.txt Inside puzzle.txt, write the following text: MWTaahyiebt_e,c__hnyaoontuc;'e_rste_r_aynr_oert_e_gasoduoipdnp_got_shoeandtl__yty_oot_uhrree__apTdrH_oItgRhrDia_sml__eowtnotere.kr_ss_. Inside puzzle2.txt, write the following text: WTTohhriikssi__niigss,___ttbhhueet___wryrioogunh'gtr__emm_eessshssoaawggieen__gff_rrtoohmme___sswaarmmoppnllgee_22o..nttexxstt Open a file specified by the user. This file will contain a bunch of characters. You should read in each character from the file, one character at a time. Display every third character on the screen. Throw the other characters away. There is a sample input file called puzzle.txt, containing a little message you can...
1. write a java program using trees(binary search treee) to read integers from input file( .txt) and add +1 to each number that you read from the input file. then copy result to another (.txt) file. example: if inpu File has numbers like 4787 79434 4326576 65997 4354 the output file must have result of 4788 79435 4326577 65998 4355 Note: there is no commas in between the numbers. dont give images or theory please.