当前位置: 首页 > 知识库问答 >
问题:

使贪婪算法在欧元硬币子集上失败

岳曦
2023-03-14

贪婪的变更算法是通过选择可用的最高面额硬币进行变更,直到达到它试图进行的变更量。令人惊讶的是,这种算法实际上是以最有效的方式改变美国和欧元硬币面额的!

然而,贪婪的算法有时会在做出改变时失败。假设我们有面额[25,15,1],并试图赚31美分。贪婪的算法会选择25,1,1,1,1,1,1 (7硬币),而31美分实际上可以制作成15,15,1(3枚硬币)。

我想知道的是,是否有一种方法可以让贪婪算法在欧元硬币的子集中失败(欧元硬币列表1,2,5,10,20,50,100,200)包括面额1。虽然我可以让贪婪算法在其他值的子集中失败,但我似乎不能让它在欧元硬币的子集中失败。

一些参考资料指出,只要最高元素加上最低元素小于第二高元素的两倍,贪婪算法就会失败(因此在上面的示例中,25 1

共有1个答案

薛文斌
2023-03-14

试着用1,20,50做60。

 类似资料:
  • 首先,是的,这是我的硬件,我觉得很难,所以我真的很感激一些指导。 我需要证明对于当

  • 问题是用硬币、一角硬币、五分硬币和一便士来换零钱,并且使用最少的硬币总数。在四个面值分别是硬币、一角硬币、五分硬币和一便士的特殊情况下,我们有c1=25、c2=10、c3=5和c4=1。 如果我们只有四分之一硬币、一角硬币和一分硬币(没有五分镍币)可供使用,贪婪算法将使用六枚硬币——四分之一硬币和五便士——兑换30美分,而我们可以使用三枚硬币,即三个一角硬币。 给定一组面额,我们如何判断贪婪方法是

  • 以人民币的硬币为例,假设硬币数量足够多。要求将一定数额的钱兑换成硬币。要求兑换硬币数量最少。 思路说明: 这是用贪婪算法的典型应用。在本例中用python来实现,主要思想是将货币金额除以某硬币单位,然后去整数,即为该硬币的个数;余数则做为向下循环计算的货币金额。 这个算法的问题在于,得出来的结果不一定是最有结果。比如,硬币单位是[1,4,6],如果将8兑换成硬币,按照硬币数量最少原则,应该兑换成为

  • 我理解硬币兑换问题的贪婪算法(用尽可能少的硬币支付特定金额)是如何工作的——它总是选择面额最大但不超过剩余金额的硬币——并且它总是为特定的硬币组找到正确的解决方案。 但对于某些硬币集,贪婪算法会失败。例如,对于集合和总和30,贪婪算法首先选择25,剩下5,然后选择5个1,总共6枚硬币。但是,对于最少数量的硬币,解决方案是选择15枚硬币两次。 一组硬币必须满足什么条件,才能让贪婪算法找到所有总数的最

  • 我试图解决换硬币的问题,你用尽可能少的硬币来换钱。我尝试使用贪婪的方法——我的算法对硬币数组进行排序,从最大的硬币开始,并尽可能多地使用它,然后再移动到下一个硬币,将剩余的硬币分开。 这对初始测试用例有效: 硬币=[1,2,5],数量=11 但这次失败了: 硬币=[186,419,83,408],金额=6249 我不确定它为什么会失败,我仍在努力掌握贪婪的方法。非常感谢您的反馈!

  • 本文向大家介绍贪婪算法相关面试题,主要包含被问及贪婪算法时的应答技巧和注意事项,需要的朋友参考一下 参考回答: 贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架,算法的关键是贪婪策