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?
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.