Java рекурсивной Оптимизация

Question

Я должен рекурсивно решить следующую задачу, используя грубую силу подхода:

Пусть выполнены два человек, А и В, имеет четное число упорядоченных коробок, каждый из которых с заданным значением. Например, boxes = {5, 3, 7, 10}. Им нужно разделить ящики между ними следующим образом: человек А выбирает либо первый, либо последний поле в наборе, тогда человек В делает то же самое и так далее, пока не останется никаких ящиков.

Лицо A хочет знать, какое максимальное значение он может получить, в совокупности, имея в виду, что при каждом повороте человек 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 

EDIT

попробовать это: (я не знаю, если тот правильный)

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

Answer 2

В этой игре в каждой точке либо для игрока 1, либо для игрока 2. Это означает, что игрок 2, максимизирующий свой собственный счет, то же, что и он сведение к минимуму оценка игрока 1. Итак, давайте возьмем счет игрока 1 как ценность игры. Вы хотите, чтобы два метода: один имитирует стратегию игрока 1, чтобы максимизировать ценность игры, в то время как другой имитирует стратегию игрока 2, чтобы минимизировать ценность игры. (Этот тип алгоритма называется Minimax algorithm.)

Не обязательно, чтобы (с жадностью) выбор наивысшего значения двух вариантов - лучшая стратегия (хотя в игровом экземпляре вы дали это, дело). Для общего решения вы действительно хотите попробовать и посмотреть, что произойдет.

В вашем коде у вас есть только один список ящиков (это один объект), который вы передаете по ссылке. Вы удаляете только предметы из него. В каждом случае у вас есть два рекурсивных вызова; когда второй называется, ваш список уже пуст. Поэтому вам придется делать копии своего списка и передавать их на рекурсивные звонки. (Или, наоборот, передайте индекс первого и последнего элементов подсписок, которые вы сейчас рассматриваете.) Вы можете сделать копию списка с:

ArrayList<Integer> copy = new ArrayList<>(boxes); 

Метод для максимизации стоимости, например, может выглядеть следующим образом:

public static int maxValue(List<Integer> boxes) 
{ 
    if (boxes.isEmpty()) 
     return 0; 

    List<Integer> boxes1 = new ArrayList<Integer>(boxes); 
    int value1 = boxes1.remove(0); 
    value1 += minValue(boxes1); 

    List<Integer> boxes2 = new ArrayList<Integer>(boxes); 
    int value2 = boxes2.remove(boxes2.size() - 1); 
    value2 += minValue(boxes2); 

    return Math.max(value1, value2); 
} 

Теперь вам нужно только minValue реализацию :-).