这个问题是np完全吗？
假设有一排 x 个装满小饰品（随机数量）的箱子，一目了然（您可以看到每个箱子中有多少小饰品）。现在有两名玩家可以在轮到他们时从两端挑选一个垃圾箱。他们不能放弃转弯。制定一个策略，让玩家获得最大数量的饰品。
x 是偶数。
这是一个 np 完全问题吗？它与布尔 SAT 类似吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这是一个非常简单的问题，并且不是NP完全问题。
这是算法的简短描述，它基于动态规划。
Can[i] - 存储饰品数量的数组。
F[i,j] - 如果只有从 i 到 j 的罐子可用，则确定最佳移动的数组。 0表示从左侧取，1表示从右侧取。
G[i,j] - 存储移动“优点”的数组。
抱歉缺少评论，但是如果您阅读一些有关动态规划的文章，您将毫无问题地理解它。
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.
Sorry for lack of comments, but if you read some articles about dynamic programming You will get it without any problem.
不，它可以通过
O(x^2)中的动态规划轻松解决。请查看此处的问题 10。No, it's easily solvable with dynamic programming in
O(x^2). Look at problem 10 here.这个问题似乎非常适合 alpha-beta 剪枝，因为很容易得出点的下限。假设玩家面对偶数个箱子。然后他可以以某种方式玩，让所有箱子都在偶数或奇数位置：
假设我们有 1 0 1 0 1 0，那么他可以拿走左边的 1，无论对手做什么，他都会继续选择增加 1。
因此，一个容易计算的下限是偶数位置上的所有 bin 的总和以及奇数位置上的所有 bin 的总和的最大值。
对于“奇数”玩家，您可以只取 (length+1)/2 最小值的总和，这不如“偶数”玩家的界限好，但也很容易计算。
我认为有了这些界限，搜索树对于实际应用来说将是稀疏的（不过，我想您总是可以找到此类问题的“病态”反例），因此解决方案应该相当快。
This problem seems to be perfect for alpha-beta-pruning, as it's easy to derive a lower bound for your points. Assume the player faces an even number of bins. Then he can play in a way either to get all bins on even or all on odd positions:
Say we have 1 0 1 0 1 0, then he can take the 1 on the left, and whatever the opponent does, he just keeps picking up the 1's.
So an easy to calculate lower bound is the maximum of the sum of all bins on even positions and the sum of all bins on odd positions.
For the "odd" player you can just take the sum of the (length+1)/2 smallest values, which is not as good as the bound for the "even" player, but as well easy to calculate.
I think with these bounds the search tree will be sparse for practical applications (I guess you can always find "pathological" counter-examples for this type of problem, though) so the solution should be quite fast.
很明显，第一个玩家有平局/获胜策略。他所要做的就是检查奇数位置箱或偶数位置箱是否具有更大的总数，然后他可以轻松地玩，迫使对手拿起“失败”奇偶的箱。
例如：
2,6,11,4,7,3
这里奇数位置更好（20 vs 13），所以玩家 1 应该选择 2。然后玩家 2 必须选择 6 或 3，它们是偶数位置。如果选择 3，则玩家 1 应选择 7，依此类推。实际上，玩家 1 应该始终选择与对手选择的位置相邻的位置，这保证了平局或获胜。
It is clear that the first player has a tie/win strategy. All he has to do is check whether the odd position bins or the even position bins have a greater total, and then he can easily play such that he forces the opponent to pick up the bins of the "losing" parity.
For example:
2,6,11,4,7,3
Here the odd positions are better(20 vs 13), so player 1 should choose 2. Then player 2 must choose either 6 or 3, which are at even positions. If 3 is chosen, player 1 should choose 7, and so on. Actually, player 1 should always choose the position next to the one chosen by his opponent, and it guarantees a tie or a win.