这个问题是np-complete吗？

Question

假设有一行x箱装满小装饰品(随机数量),在视线范围内(你可以看到每个箱子里有多少小装饰品).现在有两名球员可以轮到他们从任何一端挑选一个垃圾箱.他们不能放弃转机.想出一个让玩家获得最大数量小饰品的策略.

x是偶数.

这是一个完整的问题吗？它类似于布尔SAT吗？

Answer 1

不,它可以通过动态编程轻松解决O(x^2).在这里看问题10 .

Answer 2

这是一个非常简单的问题,并不是NP完整的.这里是算法的简短描述,它基于动态编程.

可以[i] - 存储小饰品数量的数组.
F [i,j] - 如果只有从i到j的罐头可用,则确定什么是最佳移动的阵列.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;
       }

很抱歉没有评论,但如果您阅读了一些关于动态编程的文章,您将毫无问题地获得它.