Hey guys,
I’m having a bit of a problem with the classic knapsack problem.
My assignment is split into two parts.
First, I only needed to write a method that returned the max weight of the items that the bag could hold. I have that code written and it works fine.
Next, I need to return exactly which items were put into the bag and what their individual weights are. That’s where I have my problem, because I’m not sure how to go about doing that. Any help would be greatly appreciated.
Code:
import java.util.*;
public class Project2 {
public static void main(String[] args) {
//create scanner
Scanner sc = new Scanner(System.in);
//enter number of items
System.out.println("Enter the number of items: ");
int numOfItems = sc.nextInt();
//enter the weights for each item
System.out.println("Enter the weights for each item: ");
//create array
double[] w = new double[numOfItems];
//for-loop to fill array with weights
for(int j = 0; j < numOfItems; j++){
w[j] = sc.nextDouble();
}
//enter the weight limit for the bag
System.out.println("Enter the weight limit for the bag: ");
double weightLimit = sc.nextDouble();
//final output
//maximum weight of items
System.out.println("The maximum weight of items placed in the bag is: " + m(numOfItems - 1, weightLimit, w) );
//what items are in the bag
System.out.println("The items in the bag are: ");
//The weights of the items in the bag
//System.out.println("The weights of the items in the bag are: " + m(m(numOfItems - 1, weightLimit, w));
//end of main method
}
//recursive method, according to instructions
//tells us max weight for bag
public static double m(int i, double weightLimit, double[] w){
//base cases
//i is index
//if there are 0 objects, return 0
if(i == 0){
return 0;
}
//if the weightLimit of the bag = 0, return 0
if(weightLimit == 0){
return 0;
}
//if the item at the given index is greater than the weightLimit
if(w[i] > weightLimit){
//return m(i-1, weightLimit, w) /call method
return m(i-1, weightLimit, w);
}
//return the final answer
//called method -- i-1, weightLimit, w... w[index] + method
return Math.max(m(i-1, weightLimit, w), w[i] + m(i, weightLimit - w[i], w));
//end of recursive method
}
//Hint: Use the following recursive method to return an ArrayList that consists of the elements in the bag:
public static ArrayList<Integer> m(int i, double weightLimit, double[] w){
if(i == 0){
return 0;
}
//if the weightLimit of the bag = 0, return 0
if(weightLimit == 0){
return 0;
}
//if the item at the given index is greater than the weightLimit
if(w[i] > weightLimit){
//return m(i-1, weightLimit, w) /call method
m(i-1, weightLimit, w);
}
//return the final answer
//called method -- i-1, weightLimit, w... w[index] + method
Math.max(m(i-1, weightLimit, w), w[i] + m(i, weightLimit - w[i], w));
//revise
//return the weights
for(int i = 0; i < numOfItems.length; i++){
ArrayList<Integer> itemsList = new ArrayList<Integer>();
itemsList.add(Math.max(m(i-1, weightLimit, w), w[i] + m(i, weightLimit - w[i], w)));
return itemsList[i];
}
//end of recursive method 2
}
}
“public static double” is the first required method, and that returns the first part(how much weight out of the given items can be held)
“public static ArrayList” Is the second required method. I need to return an integer arraylist that consists of the elements in the bag, and in the end I need it to say which items are in there and their weights.