algorithm - 这个问题是np-complete吗？

假设有x箱装满小饰品(随机数量)的x箱，以明眼可见(您可以看到每个箱中有多少个小饰品)。现在有两个玩家可以在轮到自己的时候从两端选择一个垃圾箱。他们不能放弃转弯。提出一种策略，让玩家获得最大数量的饰品。

x是偶数。

这是一个np完全问题吗？它与 bool SAT相似吗？

最佳答案

这是一个非常简单的问题，并且不是NP完整的。
这是算法的简短描述，它基于动态规划。

Can [i]-存储小饰品数量的数组。
F [i，j]-确定只有从i到j的 jar 头可用时，确定最佳移动方式的数组。 0表示从左侧获取，1表示从右侧获取。
G [i，j]-存储移动“好”的数组。

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

很抱歉缺少注释，但是如果您阅读了一些有关动态编程的文章，则可以毫无问题地得到它。