贪婪算法在纸牌游戏中的一个例子

Question

你玩一个新的集换式卡牌游戏。你和电脑各有一张牌。计算机放置一张卡，然后您放置卡。每张牌都有一个强度值，具有较高强度值的卡获胜。如果您和 If 计算机具有同样强大的卡，则计算机获胜。您知道计算机的卡。你的目标是计算你赢得的最大化卡牌的强度值之和。为此，您将获得两个整数数组，它们代表您的卡和计算机的卡。

你会有[5,15,100,1,5]的牌。电脑使用相同的牌，所以也使用[5,15,100,1,5]。当电脑打出100张牌时，你就下你的1张牌，因为你赢不了。如果他打出15张牌，你就下100张牌，赢了。如果他打出5张牌，你就下15张牌。如果他打出第二张5张牌，你就下5张牌，输了这一轮。如果他打出1张牌，你就用你的第5张牌进行反击。你会得到价值120英镑的获胜牌。

我的算法是:当电脑放一副牌中最大的一张牌时(这里是100)，我放最小的一张，这里是1。我会继续这样做，每当我赢了，我就会写下结果

有没有人对贪婪算法有其他建议

Answer 1

你的想法是正确的。这里还有另一点需要考虑。

对于[5，15，100，1，5]，

< li >电脑掷出5，你掷出100，因为它最大。 < li >下一台计算机掷出15点，现在您的最大点数是15点，您将失去该点数。

为了避免这种情况，您应该选择给定数字的下一个最大值。

1. 当计算机抛出 5 时，您抛出 15。
2. 当计算机抛出15时，你抛出100并得到点。

如果所有牌都是唯一的，您可以通过这种方式赢得（n-1）分，其中n是数组的大小。

因此，算法是找到下一个最大值。如果可以找到它，请返回它，否则返回数组中的最小数字。