Knapsack problem

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.

Is this a school assignment? And are you allowed to receive outside help?

2 Likes

Yes it is and yes I am

As this is a school assignment, we can only provide general guidance here on the forums.

Here are some questions to ask yourself when trying to solve this:

  • What’s the overall end goal? (You’ve just about got this answered.)
  • What are some smaller goals that lead to the end goal?
  • For each of those smaller goals, generally, what logic do you need to use to attain those goals?
  • What are the more specific steps involved in that general idea you have of how to reach these smaller goals?
1 Like