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

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

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