Optimizing recursive backtrack

Question

I solved a variation of the knapsack problem by backtracking all of the possible solutions. Basically 0 means that item is not in the backpack, 1 means that the item is in the backpack. Cost is the value of all items in the backpack, we are trying to achieve the lowest value possible while having items of every "class". Each time that a combination of all classes is found, I calculate the value of all items and if it's lower than globalBestValue, I save the value. I do this is verify().

Now I'm trying to optimize my recursive backtrack. My idea was to iterate over my array as it's being generated and return the generator if the "cost" of my generated numbers is already higher then my current best-value, therefore the combination currently being generated can't be the new best-value and can be skipped.

However with my optimization, my backtrack is not generating all the values and it actually skips the "best" value I'm trying to find. Could you tell me where the problem is?

private int globalBestValue = Integer.MAX_VALUE;
private int[] arr;

public KnapSack(int numberOfItems) {
    arr = new int[numberOfItems];
}

private void generate(int fromIndex) {
    int currentCost = 0; // my optimisation starts here
    for (int i = 0; i < arr.length; i++) {
        if (currentCost > globalBestValue) {
            return;
        }
        if (arr[i] == 1) {
            currentCost += allCosts.get(i);
        }
    } // ends here
    if (fromIndex == arr.length) {
        verify();
        return;
    }
    for (int i = 0; i <= 1; i++) {
        arr[fromIndex] = i;
        generate(fromIndex + 1);
    }
}

public void verify() {
            // skipped the code verifying the arr if it's correct, it's long and not relevant
            if (isCorrect == true && currentValue < globalBestValue) {
                globalBestValue = currentValue;
            }else{
                return;
            }
}

Answer 1

1. Pardon my bluntness, but your efforts at optimizing an inefficient algorithm can only be described as polishing the turd. You will not solve a knapsack problem of any decent size by brute force, and early return isn't enough. I have mentioned one approach to writing an efficient program on CodeReview SE; it requires a considerable effort, but you gotta do what you gotta do.

2. Having said that, I'd recommend you write the arr to console in order to troubleshoot the sequence. It looks like when you go back to the index i-1, the element at i remains set to 1, and you estimate the upper bound instead of the lower one. The following change might work: replace your code

   for (int i = 0; i <= 1; i++) {
       arr[fromIndex] = i;
       generate(fromIndex + 1);
   }
   

   with

   arr[fromIndex] = 1;
   generate(fromIndex + 1);
   arr[fromIndex] = 0;
   generate(fromIndex + 1);
   

This turns it into a sort of greedy algorithm: instead of starting with 0000000, you effectively start with 1111111. And obviously, when you store the globalBestValue, you should store the actual data which gives it. But the main advice is: when your algorithm behaves weirdly, tracing is your friend.