Hello, I am writing a java program. I don\'t know a lot of imports. Only joption

Question

Hello, I am writing a java program. I don't know a lot of imports. Only joptionapane, io, scanner.

The Knapsack Problem: A hiker has a knapsack which will hold a total of N pounds. The hiker has a number of objects weighing w1 pounds, w2 pounds, ., wr pounds which he wishes to take with him. He wants to fill the knapsack as full as possible, that is, to pack it with objects having the maximum total weight. You will implement a program to help him figure this out. To make this problenm simpler, we fix the number of objects to be 4. Follow the steps below in your program flow. It is required that vou use the for loop for this exercise, 1. Prompt the user and input the maximum number of pounds that the hiker can carry 2. Prompt the user and input the weights of the 4 objects that the hiker can choose from to take with him 3. Find the best solution, and print which objects should be taken by the hiker. (Hint: you will need to use a series of nested loops). The best solution is the combination with the highest total that does not exceed the maximum that the hiker can carry. The name of your class should be KnapsackProblem To help you test your code, here are some test cases: Max Weight 24: 5,7, 13, 17 Best Combo: 7, 17 Max Weight 25: 5, 10, 13,9Best Combo: 5, 10, 9 Max Weight 18: 4,7, 9, 13Best Combo: 4, 13 The solution to this problem will require 4 nested for loops. HINT: consider the output of the following code. what does the value of i and j signify? Think about how this could be extended to four numbers? Try to extend this to 4 nested loops, with the indices going onlv up to 2. What is the significance of the 0 in the print out?

Explanation / Answer

The required code has been given below:

import java.util.*;
class KnapsackProblem
{
public static void main(String args[])
{
Scanner sc = new Scanner (System.in);
  
System.out.print ("Enter maximum number of pounds the hiker can carry: ");
int N = sc.nextInt();
int objects[] = new int[4];
  
System.out.println();
for(int i = 0; i < 4; i++)
{
System.out.print("Enter weight of object " + (i + 1) + ": ");
objects[i] = sc.nextInt();
}
  
int selectedWeights[] = new int[4];
for(int i = 0; i < 4; i++)
{
selectedWeights[i] = 0;
}
  
//Variable to check if adding any two weights will result in going over the limit
//In that case, just the maximum single element is taken
boolean canAdd = false;
int max = objects[0] + objects[1];
int sum = max;
if (max <= N)
{
canAdd = true;
selectedWeights[0] = objects[0];
selectedWeights[1] = objects[1];
}
  
//Sum taking 2 at a time
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
if (i != j)//eliminating duplicates
{
sum = objects[i] + objects[j];
if (sum > max && sum <= N)
{
canAdd = true;
max = sum;
selectedWeights[0] = objects[i];
selectedWeights[1] = objects[j];
selectedWeights[2] = 0;
selectedWeights[3] = 0;
}
}
}
}
if (canAdd == false)
{
max = max(objects);
selectedWeights[0] = max;
selectedWeights[1] = 0;
selectedWeights[2] = 0;
selectedWeights[3] = 0;
}
  
//Sum taking 3 at a time
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
for(int k = 0; k < 4; k++)
{
if (i != j && i != k && j != k)//eliminating duplicates
{
sum = objects[i] + objects[j] + objects[k];
if (sum > max && sum <= N)
{
max = sum;
selectedWeights[0] = objects[i];
selectedWeights[1] = objects[j];
selectedWeights[2] = objects[k];
selectedWeights[3] = 0;
}
}
}
}
}
  
//Sum taking 4 at a time
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
for(int k = 0; k < 4; k++)
{
for(int l = 0; l < 4; l++)
{
if (i != j && i != k && i != l && j != k && j != l && k != l)
{
sum = objects[i] + objects[j] + objects[k] + objects[l];
if (sum > max && sum <= N)
{
max = sum;
selectedWeights[0] = objects[i];
selectedWeights[1] = objects[j];
selectedWeights[2] = objects[k];
selectedWeights[3] = objects[l];
}
}
}
}
}
}
  
//Display result
System.out.println(" For a maximum weight of " + N + " pounds");
System.out.println("and for objects of the following weights:");
System.out.println(" " + objects[0] + " lbs, " + objects[1] + " lbs, " + objects[2] + " lbs, and " + objects[3] + " lbs");
System.out.println(" The hiker can carry the following item weights: ");
System.out.println();
System.out.print(selectedWeights[0] + " lbs");
for(int i = 1; i < 4; i++)
{
if (selectedWeights[i] != 0)
{
System.out.print(", " + selectedWeights[i] + " lbs");
}
}
System.out.print(" for a total of " + max + " lbs.");
}
static int max(int arr[])
{
int m = arr[0];
for(int i = 0; i < arr.length; i++)
{
if (arr[i] > m)
{
m = arr[i];
}
}
return m;
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.