2ch吧 关注:528,914贴子:15,173,256
  • 4回复贴,共1

关于20瓶水最少花多少钱那个问题

取消只看楼主收藏回复

这个问题可以简单使用计算机算法设计中的greedy algorithm来达到最优解
我发现很多人一来就用“直接买xx瓶”来开头 按照贪婪算法的逻辑 这个问题显然一瓶一瓶买入才是最优解 每买一瓶就要检查是否可以进行兑换 所以只需要理清逻辑关系即可轻易得出答案 楼下放出python源代码以及两个问题的运行结果


IP属地:加拿大来自iPhone客户端1楼2016-05-25 09:35回复


    IP属地:加拿大来自iPhone客户端2楼2016-05-25 09:35
    收起回复
      话说有人会将代码中用瓶盖数量除以4或者空瓶子数量除以2来算兑换多少瓶水,那样计算出来10元可喝15瓶,这里面有一个逻辑漏洞,因为整个过程会出现瓶盖数以及空瓶数量为奇数的情况,这个时候用除法计算在数学中可行但是现实生活运用是不行的 因为你不可能兑换x.5瓶水出来 兑换的必然是整数。


      IP属地:加拿大来自iPhone客户端4楼2016-05-25 10:43
      收起回复
        额刚刚又想了下发现了不对劲的地方 第二题的贪婪算法应该是尽量买最多的啤酒 因此一开始就应该把10元花光来计算最多可以兑换多少瓶才对 重新算了是15瓶水没错 附上改进后的代码


        IP属地:加拿大来自iPhone客户端6楼2016-05-25 11:20
        回复


          IP属地:加拿大8楼2016-05-25 11:21
          回复