这是问题的NP完全问题？ [英] Is this problem np-complete?

问题描述

说有一个行的 X 的垃圾桶装满小饰品（随机量），在纯视线（你可以看到有多少小饰品也有在每个箱）。现在有两名球员谁可以当它是轮到他们挑选两端的垃圾桶。他们不能放弃一转。拿出一个战略，一个球员拿到饰​​品的最高金额。

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 的是偶数。

这是一个NP完全问题？难道是类似于布尔SAT？

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

推荐答案

这是非常简单的问题，它不是NP完全。 这里是算法的简短描述，它是基于动态规划。

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

可以[I] - 阵列存储饰品的数量
F [I，J] - 阵列确定什么是最好的举措如果只罐从i到j是avaible。 0手段采取从左侧，1表示需要从右侧。
政[I，J] - 阵列，其中的移动'善'是存储。

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.

这篇关于这是问题的NP完全问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！