最大化2位玩家选号之和的差值

Question

我有 2 个问题源于一个简单的问题。我会用我找到的解决方案和修改后的问题来解释简单的问题。

Suppose there is a game with 2 players, A and B and a list of positive integers. Player A starts by taking out a number from the list, player B does the same and so on after the there are no longer numbers in the list. Both players sum up the picked numbers. The goal for each player is to maximize the difference between his sum and opponent's sum, which is the score. The question is what is the maximum score player A can obtain if both players play in an optimal manner.

现在，为此我想出了每个玩家的最佳策略是在每一步取最大的数字，伪代码如下：

sumA = 0
sumB = 0
list = [1, 5, 3, 7, 9]

while list IS NOT EMPTY:
    val = pop_max(list)
    sumA = sumA + val

    if list IS NOT EMPTY:
        val = pop_max(list)
        sumB = sumB + val


scoreA = sumA - sumB
print scoreA

这可以运行 in O(n) 或 O(n*log(n)) 取决于如何列表中的数字已排序。

以下2处修改：

At the beginning of the game player A should remove K numbers from the list. If he does this in an optimal manner and after that the games is the initial one, what is the maxim score he can obtain?

和

At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?

对于第二个修改，我可以想到一种蛮力方法，即计算所有可能性的树，但这不适用于大输入数据。我相信有某种DP算法。

第一次修改想不出办法

有人可以为这 2 次修改提供一些算法思路吗？

[后期编辑]

修改2的解决方案可以在这里找到https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/是DP。

Answer 1

这里是第2次修改的post，即

At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?

解决方案基于DP。对于子问题 (i-j) 即 v[]i, v[i+1], ..., v[j] 有两个选择：

用户选择第i个值为v[i]的元素：对手要么选择第(i+1)个元素，要么选择第j个元素。对手打算选择给用户留下最小价值的元素。即用户可以收集值 v[i] + min(F(i+2, j), F(i+1, j-1))

用户选择值为v[j]的第j个元素：对手要么选择第i个元素，要么选择第(j-1)个元素。对手打算选择给用户留下最小价值的元素。即用户可以收集值 v[j] + min(F(i+1, j-1), F(i, j-2))

以下是基于以上两个选择的递归解决方案。我们取两个选项中的最大值。

F(i, j) represents the maximum value the user can collect from i-th coin to j-th coin.

F(i, j) = Max(v[i] + min(F(i+2, j), F(i+1, j-1)), v[j] + min(F(i+1, j-1), F(i, j-2)))

Base Cases

F(i, j) = v[i] If j == i

F(i, j) = max(v[i], v[j]) If j == i+1

这是 Python 中的一段代码可以解决它

def optimalStrategyOfGame(arr, n): 
  
    # Create a table to store solutions of subproblems  
    table = [[0 for i in range(n)] for i in range(n)] 

    # Fill table using above recursive formula. Note that the table is  
    # filled in diagonal fashion from diagonal elements to table[0][n-1] which is the result.  
    for gap in range(n): 
        for j in range(gap, n): 
            i = j - gap 
          
            # Here x is value of F(i+2, j), y is F(i+1, j-1) and z is  
            # F(i, j-2) in above recursive formula  
            x = 0
            if((i + 2) <= j): 
                x = table[i + 2][j] 
            y = 0
            if((i + 1) <= (j - 1)): 
                y = table[i + 1][j - 1] 
            z = 0
            if(i <= (j - 2)): 
                z = table[i][j - 2] 
            table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z)) 
    return table[0][n - 1]

[来源]https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/

最大化2位玩家选号之和的差值

Maximize the difference of the sum of picked numbers by 2 players

algorithm

dynamic-programming

pseudocode

greedy