這幾年商家為了刺激消費是變着花樣的推出各種各樣的活動，以某多多為首的營運式電商更是讓我們看到了營銷的無限“潛力”。這不，最近剛趕上雙 11，小區便利店的老王頭也推出了一項「空酒瓶子換酒」的促銷活動，它的規則是這樣的。
本文已收錄至 Github《小白學算法》系列：https://github.com/vipstone/algorithm
客戶購買 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（能朝給定總目标前進一步） { 利用可行的決策，求出可行解的一個解元素； } 由所有解元素組合成問題的一個可行解。
注意：因為用貪心算法隻能通過解局部最優解的政策來達到全局最優解，是以，一定要注意判斷問題是否适合采用貪心算法政策，找到的解是否一定是問題的最優解。
接下來我們就用代碼來示範一下貪心算法的具體實作。
首先我們先把全局問題轉換成局部問題：當空瓶子能換一瓶酒的時候，我們就換一瓶酒，實作代碼如下：
實作思路：
先把所有酒喝掉 <code>int total = numBottles</code>；
有足夠的空瓶就去換一瓶酒，執行一次 <code>while</code> 循環；
在循環中，空瓶的數量 +1，能喝到酒的數量 +1；
執行下一次循環判斷。
我們将以上代碼送出至 LeetCode，執行結果如下：
以上的貪心算法是一瓶酒一瓶酒進行循環兌換的，那我們可否每次将所有的空瓶子全部兌換完（可兌換的最大值），然後将兌換的酒再喝完，再進行下一次兌換？
答案是肯定的，我們隻需要使用取模和取餘操作就可以實作了，具體代碼如下：
貪心算法初看感覺很“難”，但具體實作起來卻發現很簡單。其實「算法」也是一樣的，初看這個詞感覺很難很高大上，其實它就是解決某個問題的一種思想、一種固定的“套路”而已，也并無神秘可言。
人常說：路雖遠行則将至，事雖然難做者必成。“難”和“易”從來都是相對的，其實從“難”到“易”就是一個逐漸開悟、逐漸成長的過程。
願你每天成長一點，最後留一個我的私人微信：GG_Stone，互相交流、共同進步。
https://leetcode-cn.com/problems/water-bottles/
https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html
https://zh.wikipedia.org/zh-hans/貪心算法
關注下面二維碼，訂閱更多精彩内容。
關注公衆号（加好友）：
作者：
王磊的部落格
出處：
http://vipstone.cnblogs.com/