H5W3
当前位置:H5W3 > 其他技术问题 > 正文

贪心算法里面的凑钱问题,如果有一张5元,三张2元,要凑6元,应该如何解?

如果先拿面额大的,那么最后就凑不出来了,怎么办呢?

回答

背包问题的所有解决思路,一言概之都是——凑。但并不代表只能凑一次,一次不行可以凑多次。
你描述的只是第一次尝试,从最大面额的开始,发现不行,就卡住了。
但是最大面额的不行了,就换面额第二大的,从头再来。
当然,硬着头皮枚举是不对的,所以需要一些优化技巧来减少计算,比如动态规划。

本文地址:H5W3 » 贪心算法里面的凑钱问题,如果有一张5元,三张2元,要凑6元,应该如何解?

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址