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

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.