时间戳

首页 > 解决方案 > 最优取K币后取最大数量的博弈

algorithm - 最优取K币后取最大数量的博弈

问题描述

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

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

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

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

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

标签： algorithmdynamic-programming

解决方案

这是一个DP方法解决方案。我们考虑n硬币，按降序排序以简化符号（意思coins[0]是最高价值的硬币，而coins[n-1]价值最低的硬币），我们想要移除k硬币以便以尽可能大的利润赢得比赛。
我们将考虑一个矩阵，每个M的维度。存储以下内容：是游戏回合后的最佳分数，此时硬币已从最佳硬币中取出。起初听起来可能有点违反直觉，但它实际上是我们正在寻找的。 事实上，我们已经有一个值来初始化我们的矩阵： 我们也可以看到n-kk
MM(i, j)iji+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) ？）。
这条路径可以为您提供您正在寻找的集合。顺便说一句，您可以看到这是有道理的，因为有k among n可能从硬币中取出k硬币的方法，并且如果您只允许向右或向下走，每个矩阵n中还有k among n从左上角到右下角的路径.kn-k
这个解释可能仍然不清楚，请不要犹豫在评论中询问精确度，我将编辑答案以更清晰。

推荐阅读