0/1Knapsack in java

Question

I am currently having trouble finding what I am doing wrong with this program. I am specifically asked to follow the directions given such as using double I, weightLimit, []W;

I continuously receive ArrayIndexOutOfBoundsException:6 as well as issues on lines 53 and 39

What is it that I am not doing correctly?

import java.util.Scanner;

public class RecursiveKnapsack {

    static double max(double a, double b) {
        if (a > b)
            return a;
        else return b;
    }

    public static double m (int i,  double weightLimit,  double [] w) {
        if(i <= 0 || weightLimit == 0) 
            return 0;
        else if (w[i] > weightLimit) 
            return m(i-1,weightLimit,w);    
        else return  max(m(i-1, weightLimit, w),w[i] + m(i-1, weightLimit-w[i], w));

    }


    public static void main (String[]args) {

        Scanner input = new Scanner(System.in);

        //NumberofItems
        System.out.println("Enter the number of items: ");

        int i = input.nextInt();

        //Weight of Items
        System.out.println("Enter the weights for each item: ");

        double[] w = new double[i];

        //Inserting input in array
        for (int x=0; x < i; x++){
            w[x] = input.nextDouble();
        }

        //Limit
        System.out.println("Enter the weight limit for the bag: ");
        double weightLimit = input.nextDouble();

        System.out.println("The maximum weight of the items placed in the bag is " + m(i,weightLimit,w));   
    }
}

possible duplicate of \https://stackoverflow.com/questions/19774594/recursive-knapsack-java-errors. — Jabongg, Feb 07 '19 at 04:40
There are several questions that this could be a duplicate of. Please provide an MCVE (https://stackoverflow.com/help/mcve) that demonstrates the problem you are having. Eliminate any parts of the code that are working correctly and are not part of the problem. — Jason, Feb 07 '19 at 04:44

Mukit09 · Accepted Answer · 2019-02-07T04:54:46.127

Your call should be like this:

m(i - 1, weightLimit, w)

instead of

m(i,weightLimit,w)

When you are calling with m(i,weightLimit,w), in m() i is not less than or equal to 0, so it is trying to access w[i]. But i'th index does not exist in the array size of i. We can access only 0 to (i-1) th index of an array.

NB: 0/1 Knapsack is a dp algorithm where memoization is must for recursive dp. But you have not done so. Also, in your base case you are returning when i = 0. But you can't do so. Because taking 0 index weight can also give you max weight.

score 0 · Answer 2 · answered Feb 07 '19 at 04:51

I agree with @mukit09's answer. Just clarifying it a bit more here.

You are getting the error because the array you are using, i.e., double w[] is of size i as you have declared. Hence the start index of the array w is 0 and ends with i-1.

But if you check in this line: else if (w[i] > weightLimit), it is trying to get the value at w[i] while actually w[i-1] is its last index. hence it gives you the ArrayIndexOutOfBounds Exception.

0/1Knapsack in java

2 Answers2