关于java:双11搞促销用贪心算法来盘他

这几年商家为了刺激生产是变着花色的推出各种各样的流动，以某多多为首的经营式电商更是让咱们看到了营销的有限“后劲”。这不，最近刚赶上双 11，小区便利店的老王头也推出了一项「空酒瓶子换酒」的促销流动，它的规定是这样的。

本文已收录至 Github《小白学算法》系列：https://github.com/vipstone/a…

客户购买 X 瓶酒，就能够用 Y 个空酒瓶来兑换一瓶新酒。

提醒：

X 和 Y 的取值如下：

1 <= X <= 100

2 <= Y <= 100

Y 值不固定，随机抽取。

如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。

请你计算 最多能喝到多少瓶酒。

示例 1：

输出：X = 9, Y = 3

输入：13

解释：你能够用 3 个空酒瓶兑换 1 瓶酒。所以最多能喝到 9 + 3 + 1 = 13 瓶酒。

示例 2：

输出：X = 15, Y = 4

输入：19

解释：你能够用 4 个空酒瓶兑换 1 瓶酒。所以最多能喝到 15 + 3 + 1 = 19 瓶酒。

示例 3：

输出：X = 5, Y = 5

输入：6

示例 4：

输出：X = 2, Y = 3

输入：2

这道题难点有两个：第一，用多少个空瓶换一瓶酒是不固定的（随机的）；第二，兑换的酒喝完之后还能持续参加兑换流动。因而要在满足这两个的前提条件下，计算本人最多能喝到几瓶。

可能有些敌人看到了本篇题目之后就晓得了解题思路，没错，咱们本文就是要用「贪婪算法」来计算最终答案。同时这道题也合乎贪婪算法的解题思路，那就是有酒瓶就兑换、能兑换多少就兑换多少。

贪婪算法（Greedy Algorithm），又称贪心算法，是一种在每一步抉择中都采取在以后状态下最好或最优（即最无利）的抉择，从而心愿导致后果是最好或最优的算法。

贪婪算法在有最优子结构的问题中尤为无效。最优子结构的意思是部分最优解能决定全局最优解。简略地说，问题可能分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

从问题的初始解登程：

while（能朝给定总指标前进一步）

{

利用可行的决策，求出可行解的一个解元素；

}

由所有解元素组合成问题的一个可行解。

留神：因为用贪婪算法只能通过解部分最优解的策略来达到全局最优解，因而，肯定要留神判断问题是否适宜采纳贪婪算法策略，找到的解是否肯定是问题的最优解。

接下来咱们就用代码来演示一下贪婪算法的具体实现。

首先咱们先把全局问题转换成部分问题：当空瓶子能换一瓶酒的时候，咱们就换一瓶酒，实现代码如下：

// 贪婪 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；
执行下一次循环判断。

咱们将以上代码提交至 LeetCode，执行后果如下：

以上的贪婪算法是一瓶酒一瓶酒进行循环兑换的，那咱们可否每次将所有的空瓶子全副兑换完（可兑换的最大值），而后将兑换的酒再喝完，再进行下一次兑换？

答案是必定的，咱们只须要应用取模和取余操作就能够实现了，具体代码如下：

// 贪婪 2：用 / 和 % 实现
class Solution {public int numWaterBottles(int numBottles, int numExchange) {
        // 总酒瓶数
        int total = numBottles;
        // 有酒瓶就兑换
        while (numBottles >= numExchange) {
            // 最多可兑换的新酒
            int n = numBottles / numExchange;
            // 累计酒瓶
            total += n;
            // 残余酒瓶(残余未兑换 + 已兑换喝掉的)
            numBottles = numBottles % numExchange + n;
        }
        return total;
    }
}

咱们将以上代码提交至 LeetCode，执行后果如下：

贪婪算法初看感觉很“难”，但具体实现起来却发现很简略。其实「算法」也是一样的，初看这个词感觉很难很高大上，其实它就是解决某个问题的一种思维、一种固定的“套路”而已，也并无神秘可言。

人常说：路虽远行则将至，事尽管难做者必成。“难”和“易”素来都是绝对的，其实从“难”到“易”就是一个逐步开悟、逐步成长的过程。

愿你每天成长一点，最初留一个我的私人微信：GG_Stone，互相交换、共同进步。

https://leetcode-cn.com/probl…

https://www.cnblogs.com/steve…

https://zh.wikipedia.org/zh-h…

关注公众号「Java 中文社群」查看更多算法图解文章。

关于java:双11搞促销用贪心算法来盘他

流动规定

解题思路

贪婪算法

贪婪算法的实现框架

代码实现 1：贪婪

代码解析

代码实现 2：贪婪改良

总结

参考 & 鸣谢