algorithm - 挑选元素游戏

Question

这是一个简单的游戏：
有一个集合，A={a1,...,an}，对手可以选择集合的第一个或最后一个元素之一，最后收集更多数字的人获胜。现在说每个参与者都尽力而为，我需要做的是编写一个动态算法来估计他们的分数。
任何想法或线索都会受到真正的赞赏。

Answer 1

这里有一个提示：要编写动态规划算法，您通常需要递归。给定

A={a1,...,an}

复发看起来像这样

f(A)= max( f({a1,...,a_n-1}) ,  f({a2,...,a_n}) )

Answer 2

实际上 dfb 给出的递归关系可能不会导致正确的答案，因为它不会导致正确的次优结构！假设玩家 A 开始游戏：他的问题结构是 [a1,a2,...an] 选择一个元素后，a1 或 an ，轮到玩家 B 下棋，然后移动之后就是玩家A的举动。所以在两步之后，玩家 A 会再次轮到他，这将是他的正确子问题。正确的递归关系将是

假设剩下 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/

Answer 3

实际上你不需要动态规划，因为很容易为上面的游戏找到一个显式的解决方案。

情况 n 是偶数或 n = 1。第二个移动的玩家总是输。

情况 n 为奇数且 n > 1。如果以下两种情况之一发生，则第二个玩家有一个获胜策略：

1. 偶数索引的元素总和大于所有奇数索引的元素

2. 除最后一个以外的所有奇数元素的总和都大于其余所有元素，并且除第一个以外的所有奇数元素的总和都大于其余所有元素。

证明草图：

情况 n 是偶数或 n = 1：令 Sodd 和 Seven 是所有具有偶数/奇数索引的元素的总和。假设 Sodd > 七，否则相同的论点成立。第一个玩家有一个获胜的策略，因为他可以以这样一种方式玩，他会得到所有奇怪的索引项目。

n 为奇数的情况，n > 1 也可以直接求解。事实上，第一个玩家有两个选择，他可以获得集合的第一个或最后一个元素。在剩余的元素中，将它们划分为具有奇数和偶数索引的两个子集；根据上面的论点，第二个玩家将选择总和最大的子集。如果你扩展树游戏，你最终会得到上面的语句。

Answer 4

示例代码

这是用于计算第一和第二玩家的最佳分数的 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，所以第一个玩家会赢（因为他得到 5 加上第一步的 3）。

然而，这个逻辑是有缺陷的，因为第二个玩家实际上可以获得更多。

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，第二位玩家获胜。

缺陷在于，虽然第二个玩家确实可以玩这样他们将赢得所有偶数或所有奇数的位置，但这不是最佳游戏，在某些情况下他们实际上可以做得更好。