采摘元素博弈
这是一个简单的游戏：
有一个集合，A={a1，...，an}，对手可以从集合的第一个或最后一个元素中选择一个，最后收集到较大数字的人获胜。现在假设每个参与者都尽了最大努力，我需要做的是编写一个动态算法来估计他们的分数。
任何想法或线索都是非常值得欣赏的。
回答 4
Stack Overflow用户
发布于 2012-11-30 17:25:56
示例代码
以下是计算第一个和第二个玩家的最佳分数的Python代码。
A=[3,1,1,3,1,1,3]
cache={}
def go(a,b):
"""Find greatest difference between player 1 coins and player 2 coins when choosing from A[a:b]"""
if a==b: return 0 # no stacks left
if a==b-1: return A[a] # only one stack left
key=a,b
if key in cache:
return cache[key]
v=A[a]-go(a+1,b) # taking first stack
v=max(v,A[b-1]-go(a,b-1)) # taking last stack
cache[key]=v
return v
v = go(0,len(A))
n=sum(A)
print (n+v)/2,(n-v)/2反例
请注意，代码包含此问题的其他答案之一的反例。
考虑案例3,1,1,3,1,1,3。
根据对称性，第一个玩家移动总是离开模式1,1,3,1,1,3。
因此，偶数元素的和是1+3+1=5，而奇数的和是1+1+3=5，因此参数是从这个位置第二个玩家将始终赢得5，第一个玩家将始终赢得5，因此第一个玩家将获胜(因为他在第一步中除了3之外还获得5)。
然而，这个逻辑是有缺陷的，因为第二个玩家实际上可以得到更多。
First player takes 3, leaves [1,1,3,1,1,3] (only choice by symmetry)
Second player takes 3, leaves [1,1,3,1,1]
First player takes 1, leaves [1,3,1,1] (only choice by symmetry)
Second player takes 1, leaves [1,3,1]
First player takes 1, leaves [3,1] (only choice by symmetry)
Second player takes 3, leaves [1]
First player takes 1所以总体来说，第一个玩家得到3+1+1+1=6，第二个玩家获得3+1+3=7，第二个玩家获胜。
缺点是，尽管第二个玩家确实可以打出他们将赢得所有偶数或所有奇数位置的游戏，但这并不是最佳游戏，在某些情况下，他们实际上可以做得更好。
Stack Overflow用户
发布于 2012-11-30 06:41:27
这里有一个提示:要编写一个动态编程算法，通常需要一个递归。给定的
A={a1,...,an}递归将如下所示
f(A)= max( f({a1,...,a_n-1}) , f({a2,...,a_n}) )Stack Overflow用户
发布于 2012-11-30 18:29:22
实际上，dfb给出的递归关系可能不会导致正确的答案，因为它不会导致正确的次优结构！假设玩家A开始游戏:在选择一个元素后，他的问题结构是a1，a2，...an，轮到玩家B玩，然后是玩家A的移动。所以在两步棋之后，玩家A会再次轮到他，这将是他的右子问题，.The右递归关系将是
假设剩下从i到j的元素：
A(i,j)= max(min( A(i+1,j-1),A(i+2,j)+a[i] ), min(A(i,j-2),A(i+1,j-1))+a[j])
请参阅以下链接：http://people.csail.mit.edu/bdean/6.046/dp/
https://stackoverflow.com/questions/13635953
复制相似问题
腾讯云开发者
