江苏龙网

  1. 首页 > 资讯 > >

双11搞促销，我们本文就是要用贪心算法来计算最终答案

双11搞促销，我们本文就是要用贪心算法来计算最终答案
文章图片

这几年商家为了刺激消费是变着花样的推出各种各样的活动 ， 以某多多为首的式电商更是让我们看到了营销的无限“潜力”
活动规则
客户购买 X 瓶酒 ， 就可以用 Y 个空酒瓶来兑换一瓶新酒 。
提示：
X 和 Y 的取值如下：
Y 值不固定 ， 随机抽取 。
如果喝掉了酒瓶中的酒 ， 那么酒瓶就会变成空的 。
请你计算 最多能喝到多少瓶酒 。
示例 1：
【双11搞促销，我们本文就是要用贪心算法来计算最终答案】双11搞促销，我们本文就是要用贪心算法来计算最终答案
文章图片

解释：你可以用 3 个空酒瓶兑换 1 瓶酒 。 所以最多能喝到 9 + 3 + 1 = 13 瓶酒 。
【双11搞促销，我们本文就是要用贪心算法来计算最终答案】示例 2：
双11搞促销，我们本文就是要用贪心算法来计算最终答案
文章图片

解释：你可以用 4 个空酒瓶兑换 1 瓶酒 。 所以最多能喝到 15 + 3 + 1 = 19 瓶酒 。
示例 3：
示例 4：
解题思路
这道题难点有两个：第一 ， 用多少个空瓶换一瓶酒是不固定的（随机的）第二 ， 兑换的酒喝完之后还能继续参与兑换活动 。 因此要在满足这两个的前提条件下 ， 计算自己最多能喝到几瓶 。
可能有些朋友看到了本篇标题之后就知道了解题思路 ， 没错 ， 我们本文就是要用贪心算法来计算最终答案 。 同时这道题也符合贪心算法的解题思路 ， 那就是有酒瓶就兑换、能兑换多少就兑换多少 。
贪心算法
贪心算法（Greedy Algorithm）又称贪婪算法 ， 是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择 ， 从而希望导致结果是最好或最优的算法 。
贪心算法在有最优子结构的问题中尤为有效 。 最优子结构的意思是局部最优解能决定全局最优解 。简单地说 ， 问题能够分解成子问题来解决 ， 子问题的最优解能递推到最终问题的最优解 。
贪心算法的实现框架
从问题的初始解出发：
while（能朝给定总目标前进一步）
利用可行的决策 ， 求出一个可行解元素 。
由所有解元素组合成问题的一个可行解 。
注意：因为用贪心算法只能通过解局部最优解的策略来达到全局最优解 ， 因此 ， 一定要注意判断问题是否适合采用贪心算法策略 ， 找到的解是否一定是问题的最优解 。
接下来我们就用代码来演示一下贪心算法的具体实现 。
代码实现 1：贪心
首先我们先把全局问题转换成局部问题：当空瓶子能换一瓶酒的时候 ， 我们就换一瓶酒 ， 实现代码如下：
// 贪心1：用 + 和 - 实现
class Solution
public int numWaterBottles（int numBottles ，int numExchange）
// 最大酒瓶数
int total = numBottles 。
// 有酒瓶就兑换
while （numBottles >= numExchange）
// 执行一轮兑换
numBottles -= numExchange 。
++total 。
// 兑换一次多一个酒瓶
++numBottles 。
return total 。
代码解析
实现思路：
先把所有酒喝掉 int total = numBottles 。
有足够的空瓶就去换一瓶酒 ， 执行一次 while 循环 。
在循环中 ， 空瓶的数量 +1 ， 能喝到酒的数量 +1 。
执行下一次循环判断 。


推荐阅读


上一篇：因为降价就大闹售楼处的老业主，河北微播报就报道了一件开发商毁约的事儿，但我觉得虽然都是缺乏契约精神

下一篇：情感|女子为买房假离婚，之后傻眼！老公竟和闺蜜…