数字选择游戏上的贪婪算法
问题给出如下：
有一个游戏具有n个数字（a1，a2，a3,..,an）和两个玩家的序列。玩家从序列中获取数字;在每个回合中，玩家可以选择序列中的第一个或最后一个数字。当序列被清空时，总和较大的玩家获胜;如果相等，则游戏为平局。
目标是编写一个算法，该算法返回一系列选择，以保证第一个玩家的最佳结果（获胜或平局），假设第二个玩家将发挥最佳状态。
我想出了一个递归公式，可以转化为动态规划解:
- 对于序列艾，艾1,...,Aj：
- 如果序列中有一个数字 - 拿走它。
- 否则，请检查两个可能的选择，选择在游戏结束时为第二个玩家提供较低结果的选项。
因此，第一个玩家的最优总和是序列中所有数字的总和减去第二个玩家将得到的最小总和。公式如下：
p（i，j） = 艾 （如果 i =j）
p(i，j) = Ai Ai 1...Aj - min{p(i 1，j)，p(i，j-1)}(如果j
我们用同样的公式计算第二个玩家和第一个玩家的和，因为第二个玩家也想得到最大可能值。
正确性可以很容易地被归纳证明。此外，我们可以从中得到动态规划解决方案：首先计算每对（i，j）的p（i，j）值，并将其保存在表nxn中。该解决方案采用 O（n^3）。此外，还有一种方法可以对总和A1 Ai 1 Ai 2进行预处理... Aj：我们可以计算总和A1 ... Aj 对于每个 j，每次应用公式 p（i，j） 都可以使用 sum（1，j） - sum（1，i），以便解将采用 O（n^2）。
有更快的算法吗？在我的解决方案中，我得到了为第一个玩家提供最大金额的选择序列，但它太“强大”了：我被要求得到一个为他带来胜利的选择序列而不管最终金额是否最大化。因此，毫无疑问，我执行了一些不必要的步骤。
更好的解决方案似乎是贪婪算法，因为我见过同样的问题，但序列中的数字是偶数（此处https://cs.stackexchange.com/questions/82351/optimizing-greedy-solution-for-choice-game/82450).
任何人都可以给我一些关于贪婪的解决方案应该是什么样子的想法或线索吗？提前感谢您！
共有2个答案
贪婪解意味着算法在每一步都选择最佳局部选项。在您的情况下，最佳局部选项意味着在第一个元素和最后一个元素之间选择最大值。
关于贪婪算法的一些思考
优点
>
实现简单
O（n）复杂度时间
骗局
> < li>
算法可能陷入局部最小值
最佳局部步骤并不总是最佳全局步骤，因此最终结果并不总是最佳结果
“贪婪”是一个简单的概念：与其查看整个游戏树，不如只考虑最大化当前关卡的短期结果。在这种情况下，这意味着采用两个可用元素中较大的一个，并且根本不使用递归。
你的完整解决方案，最大化收到的金额，工作；只是对大局来说有点矫枉过正。
两者之间的平衡可能有用，这是一种前瞻性的方法，可以预测一定数量的移动。例如，在游戏中只前进四步（每个玩家两步），然后选择能最大化你的差异的一步。
-
本文向大家介绍贪婪算法相关面试题，主要包含被问及贪婪算法时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策
-
你玩一个新的集换式卡牌游戏。你和电脑各有一张牌。计算机放置一张卡，然后您放置卡。每张牌都有一个强度值，具有较高强度值的卡获胜。如果您和 If 计算机具有同样强大的卡，则计算机获胜。您知道计算机的卡。你的目标是计算你赢得的最大化卡牌的强度值之和。为此，您将获得两个整数数组，它们代表您的卡和计算机的卡。 你会有[5,15,100,1,5]的牌。电脑使用相同的牌，所以也使用[5,15,100,1,5]。
-
有人有线索为什么它对案件2不起作用吗？非常感谢你的帮助。编辑：案例2的预期结果是6130美元。我好像得到了6090美元。
-
以下是我需要咨询以寻求帮助的问题： 编写一个贪婪算法，使用贪婪算法以尽可能少的硬币进行兑换。您将获得一个硬币值数组和一个金额：。返回一个包含每个硬币计数的数组。 例如：应该返回数组，该数组指示每枚硬币的数量：2枚50美分硬币，1枚25美分硬币，1枚10美分硬币），没有镍币（5美分），和2便士（1美分），加起来是137美分。 从computeChange返回的数组应该与第一个参数（硬币）的长度相同。
-
任务是典型的背包问题。求解时应采用贪婪算法。我设法创建了下面的代码，但它工作得太慢了。你能告诉我怎么加快速度吗？谢谢你。 c是背包的重量限制。n表示价格权重对的数量（这两个数字都是int类型，而不是float）。限制如下：（1）如果在相同重量的元素之间选择，价格最高的元素应该被取；（2）如果在相同价格和相同重量的元素之间选择，第一个输入的元素应该被取。
-
设计算法以实现给定问题的最佳解决方案。 在贪婪算法方法中，决策是从给定的解决方案域做出的。 由于贪婪，选择了似乎提供最佳解决方案的最接近的解决方案。 贪心算法试图找到一个本地化的最优解决方案，最终可能导致全局优化的解决方案。 但是，通常贪婪算法不提供全局优化的解决方案。 计数硬币 这个问题是通过选择最不可能的硬币来计算到期望的值，并且贪婪的方法迫使算法选择最大可能的硬币。 如果我们提供₹1,2,5