algorithm - 最优去除K币后选择最大数量的博弈

Question

我要解决以下任务:
两个玩家玩一个游戏。在这个游戏中有硬币，每个硬币都有一个值。每个玩家轮流选择 1 个硬币。目标是最终获得最高的总值(value)。每个玩家都被迫选择玩(这意味着总是从堆中选择最高值)。我必须找出 2 个玩家的总和/他们的最高可能总和之间的差值

约束:所有值都是自然整数和正数。

上面的任务是一个典型的贪心问题。根据我的尝试，可以使用 quickSort 对其进行排序，然后只需为 2 个玩家选择元素。如果您在我的测试中需要更好的时间，Radix-Sort 的表现会更好。好的，这个任务很简单。

现在我有与上述相同的任务，但第一个玩家必须最佳地移除 K 个硬币，以使他们的分数之间的差异最大。嗯，这听起来像 DP，但我想不出解决方案。我必须再次找出他们得分之间的最大差异(两名球员都打得最好)。或让 2 名玩家的积分相差最大。

是否已经实现了这样的算法？或者有人可以给我一些关于这个问题的提示吗？

Answer 1

这是一个 DP 方法解决方案。我们考虑 n 硬币，按降序排序以简化符号(意味着 coins[0] 是值(value)最高的硬币，而 coins[n-1] 具有最低值)，我们想要移除 k 个硬币，以便以尽可能大的利润赢得游戏。
我们将考虑一个矩阵 M，每个 k 的维度为 n-k。
M 存储以下内容:M(i, j) 是 在 i 回合后的最佳得分，当 j 硬币已从 i+j 最佳硬币 中删除。起初听起来可能有点违反直觉，但它实际上正是我们要寻找的。
事实上，我们已经有了一个值来初始化我们的矩阵:M(0, 0) = 0。
我们也可以看出M(n-k, k)其实就是我们要解决的问题的解。
我们现在需要递归方程来填充我们的矩阵。我们认为我们想要最大化第一个玩家的得分差异。为了使第二位玩家的分数差最大化，方法是一样的，只是修改一些标志。

if i = 0 then:
    M(i, j) = 0  // score difference is always 0 after playing 0 turns
else if j = 0 and i % 2 = 0:  // player 1 plays
    M(i, j) = M(i-1, j) + coins[i+j]
else if j = 0 and i % 2 = 1:  // player 2 plays
    M(i, j) = M(i-1, j) - coins[i+j]
else if i % 2 = 0:
    M(i, j) = max(M(i, j-1), M(i-1, j) + coins[i+j])
else if i % 2 = 1:
    M(i, j) = max(M(i, j-1), M(i-1, j) - coins[i+j])

这种循环简单地意味着，在任何时候，最好的选择是取走硬币(在最佳值为 M(i, j-1) 的情况下)，或不取走硬币它(最佳值为 M(i-1, j) +/- coins[i+j] 的情况)。
这会给你最终的得分差异，但不是要移除的硬币组。要找到它，您必须保留程序用于计算矩阵值的“最佳路径”(最佳值是来自 M(i-1,j) 还是来自 M(i,j-1) ？)。< br/>此路径可以为您提供您正在寻找的集合。顺便说一下，你可以看出这是有道理的，因为有 k amongn 种可能的方法可以从 n 硬币中移除 k 硬币，并且在每个 n-k 矩阵的 k 中，还有从左上角到右下角的 k among 路径，如果你被允许向右走，或者仅向下。
这个解释可能仍然不清楚，请不要犹豫，在评论中询问精确度，我会编辑答案以便更清楚。