Java 递归优化

Question

我必须使用暴力方法递归地解决以下问题:

假设两个人 A 和 B 有偶数个有序盒子，每个盒子都有给定的值。例如，boxes = {5, 3, 7, 10} 。他们需要以这种方式在他们之间分割盒子:A 选择集合中的第一个或最后一个盒子，然后 B 做同样的事情，依此类推，直到没有剩下的盒子。

人 A 想知道他总共可以获得的最大值(value)是多少，同时记住，人 B 在每个回合也可以做出两个选择。换句话说，问题是提出一种算法来模拟两个人的所有选择，考虑到他们都希望获得长期的最大值。

所以，现在我有这个:

public static int maxValue(ArrayList <Integer> boxes, int choice, int person){
    int value;

    //Stop condition - if there are no more boxes, return 0
    if (boxes.isEmpty())
        return 0;

    if (choice == 0) //Person chose the first box in the sequence
        value = boxes.remove(0);
    else //Person chose the last box in the sequence
        value = boxes.remove(boxes.size() - 1);

    //Person A makes a choice, checking which one works best in the long run
    if (person == 1)
        return (value + max(maxValue(boxes, 0, 2), maxValue(boxes, 1, 2)));

    //Person B makes a choice, checking which one works best in the long run
    else
        return (value + max(maxValue(boxes, 0, 1), maxValue(boxes, 1, 1)));
}

对于输入 boxes = {5, 3, 7, 10} ，代码应该产生 15，但我上面写的代码却给出了 25。在放置一些调试打印后，我看到它是这样的:

->Person A chooses '10'
->Person B chooses '7'
->Person A chooses '3'
->Person B chooses '5'

然后将所有值相加。我认为这是因为 A 引用 B 调用该函数的方式(在 max(maxValue(boxes, 0, 2), maxValue(boxes, 1, 2)) 中)，反之亦然，而且还因为停止条件(如果我稍微改变它，返回的值是不同的)。

如果有人可以看一下并告诉我您的想法，我将不胜感激。 谢谢!

Answer 1

您真的只是想知道 person1 有什么？

        public static final Integer boxes[] = { 5, 3, 7, 10 };

public static void main(String[] args) {
    List<Integer> asList = new ArrayList<Integer>(Arrays.asList(boxes));
    System.out.println(getMaxValue(asList, 0, 0, true));
}

private static int getMaxValue(List<Integer> box, int sumPers1, int sumPers2, boolean isPers1Turn) {
    int chosenBoxIndex;
    if (box.get(0) > box.get(box.size() - 1)) {
        chosenBoxIndex = 0;
    } else {
        chosenBoxIndex = box.size() - 1;
    }
    Integer chosenBoxValue = box.remove(chosenBoxIndex);

    if (isPers1Turn) {
        sumPers1 += chosenBoxValue;
        System.out.println("Pers1 chose: " + chosenBoxValue + " now has a total of " + sumPers1);
    } else {
        sumPers2 += chosenBoxValue;
        System.out.println("Pers2 chose: " + chosenBoxValue + " now has a total of " + sumPers2);
    }
    if (box.size() == 0) {
        return sumPers1;
    }
    return getMaxValue(box, sumPers1, sumPers2, !isPers1Turn);
}

-->

 Pers1 chose: 10 now has a total of 10 
 Pers2 chose: 7 now has a total of 7 
 Pers1 chose: 5 now has a total of 15 
 Pers2 chose: 3 now has a total of 10 
 15

编辑

试试这个:(我真的不知道这是否正确)

public static void main(String[] args) {
    List<Integer> asList = new ArrayList<Integer>(Arrays.asList(boxes));
    System.out.println(getMaxValueXX(asList, 0, 0, true));
}

private static int getMaxValueXX(List<Integer> box, int sumPers1, int sumPers2, boolean isPers1Turn) {

    int path1 = getMaxValue(box, sumPers1, sumPers2, isPers1Turn, 0);

    int path2 = getMaxValue(box, sumPers1, sumPers2, isPers1Turn, box.size() - 1);

    if (path1 > path2) {
        return path1;
    }

    return path2;

}

private static int getMaxValue(List<Integer> origBox, int sumPers1, int sumPers2, boolean isPers1Turn, int chosenBoxIndex) {
    List<Integer> box = new ArrayList<Integer>(origBox);
    Integer chosenBoxValue = box.remove(chosenBoxIndex);
    if (isPers1Turn) {
        sumPers1 += chosenBoxValue;
        // System.out.println("Pers1 chose: " + chosenBoxValue +
        // " now has a total of " + sumPers1);
    } else {
        sumPers2 += chosenBoxValue;
        // System.out.println("Pers2 chose: " + chosenBoxValue +
        // " now has a total of " + sumPers2);
    }
    if (box.isEmpty()) {
        System.out.println("Value at the end for pers1: " + sumPers1);
        return sumPers1;
    }
    return getMaxValueXX(box, sumPers1, sumPers2, !isPers1Turn);
}