6

假设有一排x 个装满小饰品（随机数量）的箱子，一目了然（你可以看到每个箱子里有多少小饰品）。现在有两名玩家可以在轮到他们时从任一端选择一个垃圾箱。他们不能放弃转弯。想出一个策略让玩家获得最大数量的小饰品。

x是偶数。

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

4

4 回答 4

5

不，它很容易通过O(x^2). 看这里的问题 10 。

于 2010-06-25T10:02:37.453 回答
5

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

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

抱歉没有评论，但是如果您阅读了一些有关动态编程的文章，您将毫无问题地得到它。

于 2010-06-25T10:07:27.277 回答
0

这个问题似乎非常适合 alpha-beta-pruning，因为很容易得出您的点的下限。假设玩家面对偶数个垃圾箱。然后他可以以一种方式让所有箱子都在偶数位置或全部在奇数位置：

假设我们有 1 0 1 0 1 0，那么他可以拿左边的 1，而无论对手怎么做，他就一直拿 1。

因此，一个易于计算的下限是偶数位置上所有 bin 的总和与奇数位置上所有 bin 的总和的最大值。

对于“奇数”玩家，您可以只取 (length+1)/2 最小值的总和，这不如“偶数”玩家的界限好，但也很容易计算。

我认为有了这些界限，搜索树对于实际应用来说将是稀疏的（不过，我猜你总能找到这类问题的“病态”反例），所以解决方案应该很快。

于 2010-06-25T11:43:41.537 回答
0

很明显，第一个玩家有一个平局/获胜策略。他所要做的就是检查奇数位置的箱子或偶数位置的箱子是否有更大的总数，然后他可以轻松地迫使对手拿起“输”平价的箱子。

例如：

2,6,11,4,7,3

这里奇数位置更好（20 vs 13），所以玩家1应该选择2。然后玩家2必须选择6或3，它们在偶数位置。如果选择 3，玩家 1 应该选择 7，依此类推。实际上，玩家 1 应该总是选择他的对手选择的位置旁边的位置，这保证了平局或胜利。

于 2010-06-25T22:10:53.483 回答