0

This is the error I'm getting.
Exception in thread "main" java.lang.StackOverflowError
at knapsack.knap.knap(knap.java:16)

I would really apprciate the help. Thanks in advance.

package knapsack;
import javax.swing.JOptionPane;
public class knap {
    static int N;             // Number of items
    static int [] size;
    static int [] val;
    static int [] maxKnown;   // Value for best knapsack of a weight
    static int [] itemKnown;  // Item that brought us up to the weight

    static int knap(int M){
        int i, space, max=Integer.MIN_VALUE, maxi = 0, t;
        if (maxKnown[M] >= 0)
            return maxKnown[M];
        for (i = 1; i <= N; i++)
            if ((space = M-size[i]) >= 0)
                if ((t = knap(space) + val[i]) > max){
                    max = t;
                    maxi = i;
                }
        maxKnown[M] = max;
        itemKnown[M] = maxi;
        return max;
    }

    public static void main(String[] args){
        int cap = Integer.parseInt(JOptionPane.showInputDialog("What is the capasity of the bag?")), wt;
        N = Integer.parseInt(JOptionPane.showInputDialog("How many items?"));
        size = new int [N + 2];
        val = new int [N + 2];
        maxKnown = new int [cap + 1];
        itemKnown = new int [cap + 1];

        for (int i = 0; i < N; i++){
            size[i] = Integer.parseInt(JOptionPane.showInputDialog("Size of item #" + (i+1) + "?"));
            val[i] = Integer.parseInt(JOptionPane.showInputDialog("Value of item #" + (i+1) + "?"));
        }

        System.out.println ("Capacity:  " + cap);
        System.out.println ("\nAvailable items:");
        for (int i = 0; i < N; i++)
        {
            System.out.printf("%d:  (%d size, %d val)\n", i, size[i], val[i]);
        }

        N++;
        size[N] = 1;
        val[N] = 0;
        for (int i = 1; i <= cap; i++)
            maxKnown[i] = -1;

        System.out.print("\nOptimal value is ");
        System.out.println(knap(cap));

        for ( wt = cap; wt > 0; )
        {
            int i = itemKnown[wt];
            System.out.printf ("%d:  (%d wt, %d val)\n", i, size[i],val[i]);
            wt -= size[i];
      }
    }        
}

Edited by SimpleIntellect: n/a

2
Contributors
1
Reply
2
Views
6 Years
Discussion Span
Last Post by NormR1
0

StackOverflowError

Those usually occur when there are recursive calls in the program.
Is knap() calling knap() too many times? Put in a counter and use println() to show what is happening.

Edited by NormR1: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.