两名玩家轮流选择一枚外部硬币。最后我们计算差异 假设两名玩家发挥最佳，他们得到的分数之间的差值。 获得最大值的贪婪策略。在我的例子中，硬币的值(value)通常不会带来最好的结果。
现在我开发了一种算法:
示例:{9,1,15,22,4,8}
我们计算偶数索引中的硬币和奇数索引中的硬币的总和。
比较两个和，(9+15+4)<(1+22+8)，所以奇数之和更大。然后我们选择索引为奇数的硬币，在我们的样本中为 8。
表现最佳的对手会尝试选择更大的硬币，例如9.
对手结束后总会有一个奇数索引的硬币，所以我们继续挑选硬币 在奇数索引处，该值为 1。
循环上述步骤，我们将得到 (8+1+22) - (9+15+4) = 3 的差值。
6.如果步骤 2 中偶数之和更大，则反之亦然。
我将我的算法生成的结果与类似于以下算法的第二种算法进行了比较:https://www.geeksforgeeks.org/optimal-strategy-for-a-game-set-2/?ref=rp
结果是一致的，直到我的测试生成了一个随机长数组: [6, 14, 6, 8, 6, 3, 14, 5, 18, 6, 19, 17, 10, 11, 14, 16, 15, 18, 7, 8, 6, 9, 0, 15, 7 , 4, 19, 9, 5, 2, 0, 18, 2, 8, 19, 14, 4, 8, 11, 2, 6, 16, 16, 13, 10, 19, 6, 17, 13, 13 , 15, 3, 18, 2, 14, 13, 3, 4, 2, 13, 17, 14, 3, 4, 14, 1, 15, 10, 2, 19, 2, 6, 16, 7, 16 , 14, 7, 0, 9, 4, 9, 6, 15, 9, 3, 15, 11, 19, 7, 3, 18, 14, 11, 10, 2, 3, 7, 3, 18, 7 , 7, 14, 6, 4, 6, 12, 4, 19, 15, 19, 17, 3, 3, 1, 9, 19, 12, 6, 7, 1, 6, 6, 19, 7, 15 , 1, 1, 6]
我的算法生成了 26 作为结果，而第二个算法生成了 36。 我的与动态编程无关，它需要更少的内存，而我还通过内存实现了第二个。 这很令人困惑，因为我的方法对于大多数数组情况都是正确的，直到这一次。 任何帮助将不胜感激!
最佳答案
如果数组的长度是偶数，您的算法会尝试产生有保证的胜利。你可以很容易地证明这一点。但这并不一定会产生最佳胜利。特别是，它不会找到您想要一些硬币位于偶数索引而其他硬币位于奇数索引的策略。
下面的简短示例说明了这一点。
[10, 1, 1, 20, 1, 1]
你的算法将考虑偶数与赔率，意识到10+1+1 < 1+20+1并首先取出最后一个元素。通过10保证获胜.
但是您想要 10和 20 。因此，最优策略是采取 10离开1, 1, 20, 1, 1 ，无论对方带哪一边，您都带对方到达 1, 20, 1 ，然后无论对方走哪一边，你就走中间。结果你得到10, 1, 20另一个人得到 1, 1, 1 。通过28保证获胜.
关于algorithm - 两人硬币游戏的最佳策略，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/62200416/