Respuesta :
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
