Is this problem np-complete?

Question

Say there is a line of x bins filled with trinkets (random amount), in plain-sight (you can see how many trinkets there are in each bin). Now there are two players who can when it's their turn pick a bin from either end. They cannot forgo a turn. Come up with a strategy for a player to get the maximum amount of trinkets.

x is even.

Is this a np-complete problem? Is it similar to boolean SAT?

Answer 1

No, it's easily solvable with dynamic programming in O(x^2). Look at problem 10 here.

Answer 2

It is very simple problem, and it is not NP complete. Here is short description of algorithm, it is based on dynamic programming.

Can[i] - array which stores number of trinkets.
F[i,j] - array determining what is best move if only cans from i to j are avaible. 0 means take from the left side, 1 means take from the right side.
G[i,j] - array where 'goodness' of move is stored.

for (i=1 to n) F[i,i] = 0
for (i=1 to n) G[i,i] = Can[i]

for (i=1 to n-1)
   for (j=1 to n-i)
       tmp1 = Can[j] - G[j+1,j+i]
       tmp2 = Can[j+i] - G[j,j+i-1]
       if (tmp1>tmp2)
       {
             F[j,j+i] = 0;
             G[j,j+i] = tmp1;
       }
       else
       {
             F[j,j+1] = 1;
             G[j,j+i] = tmp2;
       }

Sorry for lack of comments, but if you read some articles about dynamic programming You will get it without any problem.

Answer 3

This problem seems to be perfect for alpha-beta-pruning, as it's easy to derive a lower bound for your points. Assume the player faces an even number of bins. Then he can play in a way either to get all bins on even or all on odd positions:

Say we have 1 0 1 0 1 0, then he can take the 1 on the left, and whatever the opponent does, he just keeps picking up the 1's.

So an easy to calculate lower bound is the maximum of the sum of all bins on even positions and the sum of all bins on odd positions.

For the "odd" player you can just take the sum of the (length+1)/2 smallest values, which is not as good as the bound for the "even" player, but as well easy to calculate.

I think with these bounds the search tree will be sparse for practical applications (I guess you can always find "pathological" counter-examples for this type of problem, though) so the solution should be quite fast.

Answer 4

It is clear that the first player has a tie/win strategy. All he has to do is check whether the odd position bins or the even position bins have a greater total, and then he can easily play such that he forces the opponent to pick up the bins of the "losing" parity.

For example:

2,6,11,4,7,3

Here the odd positions are better(20 vs 13), so player 1 should choose 2. Then player 2 must choose either 6 or 3, which are at even positions. If 3 is chosen, player 1 should choose 7, and so on. Actually, player 1 should always choose the position next to the one chosen by his opponent, and it guarantees a tie or a win.