你玩一个新的纸牌游戏。你和电脑各有一副牌。电脑放一张牌，然后你放你的牌。每一张牌都有一个强度值，强度值越高的牌获胜。如果你和if电脑有同样强的牌，电脑就赢了。你知道电脑的卡片。你的目标是计算你赢得的牌的强度值的总和。为此，您得到两个整数数组，它们代表您的卡和计算机的卡。
你会得到卡片[5，15，100，1，5]。计算机使用相同的卡，因此[5，15，100，1，5]。当电脑排100时，你就排1，因为你赢不了。如果他出15分，你出100分，你就赢了。如果他5岁，那么你15岁。如果他打出第二个5，那么你拿到5，这一轮就输了。如果他把他的1，你用你的第五个总数。你将得到价值120英镑的中奖牌。
任务：描述你的贪心算法的想法，可以计算总和。
我的算法是：当计算机从它的卡片组中放入最大的卡片（在本例中为100）时，我在本例中放入最小的数字1。我会继续这样做，在最后我会写，每当我赢了，加上结果
有人对贪婪算法有其他建议吗
1条答案
按热度按时间d6kp6zgx1#
你的想法是对的。这里还有另外一点需要思考。
对于[5，15，100，1，5]，
计算机抛出5，你抛出100，因为它是最大的。
下一台电脑掷15分，现在你的最大值是15分，你会失去分数。
为了避免这种情况，您应该选择给定数字的下一个最大值。
当计算机抛出5，你抛出15。
当电脑投15分时，你投100分就得到了分数。
如果所有的牌都是唯一的，你可以通过这种方式赢得（n-1）点，其中n是数组的大小。
所以，算法就是找到下一个最大值。如果可以找到它，则返回它，否则返回数组中的最小数字。