Java Recursive Optimization

Question

I have to recursively solve the following problem, using a brute force approach:

Suppose two people, A and B, have an even number of ordered boxes, each with a given value. For example, boxes = {5, 3, 7, 10}. They need to split the boxes between them, in this way: person A chooses either the first or the last box in the set, then person B does the same, and so on until there are no boxes left.

Person A wants to know, what's the maximum value he can get, in total, bearing in mind that at each turn person B can make two choices as well. In other words, the problem is to come up with an algorithm that simulates all the choices of both people, considering they're all aiming to have the maximum value in the long term.

So, for now I have this:

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

For an input of boxes = {5, 3, 7, 10}, the code is supposed to produce 15, yet the one I wrote above gives me 25. After placing some debugging prints, I saw it goes:

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

And then just adds all the values. I'm figuring it's because of the way the function is called by person A with reference to person B (in max(maxValue(boxes, 0, 2), maxValue(boxes, 1, 2))), and vice-versa, and also because of that stop condition (if I change it slightly the value returned is different).

I'd greatly appreciate it if anyone could take a look and maybe tell me what you think. Thank you!

I'm voting to close this question as off-topic because it belongs on codereview.stackexchange.com. — user1907906
– user1907906, Commented Feb 19, 2015 at 7:52
Your question is contradicting. regardless of the choices of person B and simulates all the choices of both people which one is it? — Stephan Bijzitter
– Stephan Bijzitter, Commented Feb 19, 2015 at 7:53
@LutzHorn I'll delete it and place it there, then! I'm sorry, I wasn't even aware of codereview's existance — M. M. F.
– M. M. F., Commented Feb 19, 2015 at 7:55
@StephanBijzitter It simulates all the choices of both people because it needs to check what happens if the second person chooses one or the other option. I see how I may have been unclear, I'll change that — M. M. F.
– M. M. F., Commented Feb 19, 2015 at 7:56
Okay, it is clear now. But you do not need to know all choices because you just want the maximum, thus you would always let person 1 pick the best option and person 2 pick the worst option. You would not even need recursion in this case — Stephan Bijzitter
– Stephan Bijzitter, Commented Feb 19, 2015 at 8:42

griFlo · Accepted Answer · 2015-02-19 09:45:05Z

You really just wann know what person1 has?

        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

try this: (i don't really know if thats correct)

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

Thank you, that works well assuming that each person makes their choice based on the values they can choose from at the moment (they choose the biggest value every time). The thing is, the function should consider the whole of the values and choices everytime. For example, for boxes = {10, 150, 3, 7, 9, 9}, if they choose solely based on what they can at the moment, person A gets a final value of 26 and person B of 162 (because A chose 10 first instead of choosing 9 in order to prevent B from keeping the largest value, 150). I'm not sure if I'm making myself clear enough, sorry

Hoopje · Accepted Answer · 2015-02-19 09:33:53Z

In this game every point is either for player 1 or for player 2. That means, that player 2 maximizing his own score is the same as him minimizing player 1's score. So let's take player 1's score as the value of the game. You want two methods: one simulates player 1's strategy of trying to maximize the game's value, while the other simulates player 2's strategy of trying to minimize the game's value. (This kind of algorithm is called a Minimax algorithm.)

It is not necessarily the case that (greedily) picking the highest value of the two options is the best strategy (although in the game instance you gave this happens to be the case). For a general solution, you really want to try both out and see what happens.

In your code, you only have one list of boxes (it's a single object), which you pass around by reference. You only remove items from it. In each turn you have two recursive calls; when the second is called your list is already empty. So you will have to make copies of your list and pass those to the recursive calls. (Or, alternatively, pass the index of the first and the last element of the sublist you are currently considering.) You can make a copy of the list with:

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

The method for maximizing the value could for example look like:

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

Now you only need a minValue implementation :-).

Collectives™ on Stack Overflow

Java Recursive Optimization

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related