我在背包问题的递归中得到不同的值

Question

背包问题我写了两段代码。第一个代码给了我正确答案（16），第二个没有。是不是我的递归函数有问题？

第一个代码（正确答案）：

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
        {
            //get maximum value
            return Math.max(sack(i-1, cap), value[i] + sack(i-1, cap - weight[i]));
        }
    }

    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);
    }

}

第二个代码（错误答案）：

public class knapsackProblem {

    static int[] weight = {1,2,4,2,5};
    static int[] value = {5,3,5,3,2};
    int result = 0;
    int tempNO = 0;
    int tempYES = 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
        {
            //no case, move on to next value
            tempNO = sack(i-1, cap);

            //yes case, add the current value and move on to next value with decreased capacity
            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);
    }

}

唯一的区别是，在第二个代码中，我在比较最大值之前将递归的结果放入变量中。

谢谢

Answer 1

您的变量是 class 的属性。递归调用每次都会修改这些属性，因为您正在使用 class 的一个实例来调用函数。在方法内声明变量并将它们从 class 中删除以使其工作。 :)

我在背包问题的递归中得到不同的值

I get different value in recursion for knapsack problem

java

recursion

knapsack-problem