背包问题递归实现结果不一致求助：两段代码仅变量存储有差异

Hey there! I see the issue with your second knapsack implementation—let's break it down clearly.

The problem boils down to shared class member variables (tempNO and tempYES). When working with recursive functions, each call creates its own isolated execution context (stack frame). But since tempNO and tempYES belong to the knapsackProblem instance, every recursive call modifies the same set of variables. This leads to accidental value overwriting during the recursive traversal: by the time you call Math.max(tempNO, tempYES), the values stored in those variables aren't the ones you intended from the current branch of recursion.

Let's compare your two implementations to make this concrete:

• In your first (working) code, you directly pass the results of recursive calls to Math.max(). Each recursive call's return value stays isolated to that specific call—no shared variables mean no cross-branch interference.
• In the second code, when you run:

  tempNO = sack(i-1, cap);
  tempYES = value[i] + sack(i-1, cap - weight[i]);
  

  The call to sack(i-1, cap - weight[i]) will itself trigger more recursive calls, which modify tempNO and tempYES repeatedly. By the time you get to the Math.max line, tempNO is no longer the original result of sack(i-1, cap)—it's been overwritten by nested recursive calls from the tempYES calculation.

The Fix #

The solution is straightforward: turn tempNO and tempYES into local variables inside the sack method instead of class members. This way, each recursive call has its own copy of these variables, which won't interfere with other branches of the recursion.

Here's the corrected version of your second code:

public class knapsackProblem {
    static int[] weight = {1,2,4,2,5};
    static int[] value = {5,3,5,3,2};
    int result = 0;

    // recursive function
    public int sack(int i, int cap) {
        //base case
        if(i<0 || cap == 0) {
            return 0;
        } else if(weight[i] > cap) {
            return sack(i-1, cap);
        } else {
            // Use local variables instead of class members
            int tempNO = sack(i-1, cap);
            int tempYES = value[i] + sack(i-1, cap - weight[i]);
            //get maximum value
            return Math.max(tempNO, tempYES);
        }
    }

    public static void main(String[] args) {
        int capacity = 10;
        int len = weight.length;
        knapsackProblem kp = new knapsackProblem();
        int total = kp.sack(len - 1, capacity);
        System.out.println("sacked array is " + total); // Outputs 16 correctly
    }
}

Recursive functions rely on isolated execution contexts for correctness. Using shared instance variables in recursion is a common pitfall because it breaks that isolation—always prefer local variables for values specific to a single recursive call.

内容的提问来源于stack exchange，提问作者Isaac