采摘元素博弈
采摘元素博弈
提问于 2012-11-30 06:30:15
这是一个简单的游戏：
有一个集合，A={a1，...，an}，对手可以从集合的第一个或最后一个元素中选择一个，最后收集到较大数字的人获胜。现在假设每个参与者都尽了最大努力，我需要做的是编写一个动态算法来估计他们的分数。
任何想法或线索都是非常值得欣赏的。
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提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/13635953
复制相关文章
相似问题
腾讯云开发者
