Issue with ArrayIndexOutOfRange

Question

I am trying to implement this pseudocode:

ALGORITHM BruteForce (Weights [1 ... N], Values [1 ... N], A[1...N]) //Finds the best possible combination of items for the KP //Input: Array Weights contains the weights of all items Array Values contains the values of all items Array A initialized with 0s is used to generate the bit strings //Output: Best possible combination of items in the knapsack bestChoice [1 .. N]

for i = 1 to 2^n do 
    j = n
    tempWeight = 0 
    tempValue = 0
    while ( A[j] != 0 and j > 0)
        A[j] = 0
        j = j–1 
    A[j] = 1
    for k = 1 to n do
        if (A[k] = 1) then
            tempWeight = tempWeight + Weights[k]
            tempValue = tempValue + Values[k]
    if ((tempValue > bestValue) AND (tempWeight <= Capacity)) then
            bestValue = tempValue 
            bestWeight = tempWeight
            bestChoice = A 
return bestChoice

Here is my try at it:

public class BruteForce {

    public static final int CAPACITY = 50;

    public static double[] bruteForce(double[] weights, double[] values, double[] A) {
        int n = weights.length;
        int j;
        double[] bestChoice = null;
        double tempWeight;
        double tempValue;
        double bestValue = 0;
        double bestWeight = 0;

        for (int i = 1; i < Math.pow(2, n); i++) {
            j = n;
            tempWeight = 0;
            tempValue = 0;
            // Here is the issue of ArrayIndexOutOfBounds: 3
            while (A[j] != 0 && j > 0) {
                A[j] = 0;
                j = j - 1;
            }
            A[j] = 1;
            for (int k = 1; k < n; k++) {
                if (A[k] == 1) {
                    tempWeight = tempWeight + weights[k];
                    tempValue = tempValue + values[k];
                }
            }
            if ((tempValue > bestValue) && (tempWeight <= CAPACITY)) {
                bestValue = tempValue;
                bestWeight = tempWeight;
            }
            bestChoice = A;
        }

        return bestChoice;

    }

    public static void main(String[] args) {
        double[] weights = { 10, 20, 15 };
        double[] values = { 5, 10, 30 };
        double[] A = new double[weights.length];
        BruteForce.bruteForce(weights, values, A);

    }

}

I keep on getting an ArrayIndex out of bounds. But I don't know why A's length is set to weights length so there shouldn't be any error in my mind. What am I doing wrong? This is an algorithm for solving the knapsack problem btw. Just in case anyone is familiar with it and would offer any critiquing of this algorithm.

EDIT: I've changed this:
          while (A[j-1] != 0 && j > 0) {
              A[j] = 0; // This would need to be changed too then right? 
              j = j - 1;
          }
          A[j-1] = 1; // This changed

Look at the line j = n;. That's equivalent to j = weights.length; You then use A[j], and A has the same length as weights. So that will always fail. Arrays are zero-indexed in Java. — Jon Skeet
– Jon Skeet, Commented Mar 7, 2017 at 17:16
you translated 2n to Math.pow(2,n) meaning 2^n. Is that what the algorithm meant ? — Jeremy Grand
– Jeremy Grand, Commented Mar 7, 2017 at 17:26
Yes. When I copied over the pseudocode, it eliminated the ^. I have updated the question. Thank you for pointing that out. — XXIV
– XXIV, Commented Mar 7, 2017 at 17:33
You misunderstood Jon Skeet's point. You should jave int j = n - 1; to avoid the ArrayOutOfBoundException. EDIT : It's rather the translation from the [1..N] in pseudocode to [0..n[ that breaks. — Jeremy Grand
– Jeremy Grand, Commented Mar 7, 2017 at 17:40

LppEdd · Accepted Answer · 2017-03-07 17:18:02Z

0

In your example j = 3
Arrays positions start at 0

A[0]
A[1]
A[2]

You need a -1

answered Mar 7, 2017 at 17:18

LppEdd

21.3k12 gold badges90 silver badges161 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

XXIV Over a year ago

So I can't start from the end of the array is what you're saying? I have to iterate from the beginning to end?

LppEdd Over a year ago

No, you just have to do j = n - 1

XXIV Over a year ago

Do you mind checking out my edit to see if I implemented it correctly?

Collectives™ on Stack Overflow

Issue with ArrayIndexOutOfRange

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related