对于背包问题，递归得到不同的值

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

您的变量是该类的属性。递归调用每次都会修改这些属性，因为您使用的是类的单个实例来对该函数进行调用。在方法中声明变量，并将其从类中删除以使其起作用。 :)