[[351760]]

本文轉載自微信公眾號「Java中文社群」，作者磊哥。轉載本文請聯系Java中文社群公眾號。   

這幾年商家為了刺激消費是變著花樣的推出各種各樣的活動，以某多多為首的運營式電商更是讓我們看到了營銷的無限“潛力”。

這不，最近剛趕上雙 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(能朝給定總目標前進一步)

{

利用可行的決策，求出一個可行解元素;

}

由所有解元素組合成問題的一個可行解。

注意：因為用貪心算法只能通過解局部最優解的策略來達到全局最優解，因此，一定要注意判斷問題是否適合采用貪心算法策略，找到的解是否一定是問題的最優解。

接下來我們就用代碼來演示一下貪心算法的具體實現。

代碼實現 1：貪心

首先我們先把全局問題轉換成局部問題：當空瓶子能換一瓶酒的時候，我們就換一瓶酒，實現代碼如下：

// 貪心1：用 + 和 - 實現 
class Solution { 
    public int numWaterBottles(int numBottles, int numExchange) { 
        // 最大酒瓶數 
        int total = numBottles; 
        // 有酒瓶就兌換 
        while (numBottles >= numExchange) { 
            // 執行一輪兌換 
            numBottles -= numExchange; 
            ++total; 
            // 兌換一次多一個酒瓶 
            ++numBottles; 
        } 
        return total; 
    } 
} 

代碼解析

實現思路：

1. 先把所有酒喝掉 int total = numBottles;
2. 有足夠的空瓶就去換一瓶酒，執行一次 while 循環;
3. 在循環中，空瓶的數量 +1，能喝到酒的數量 +1;
4. 執行下一次循環判斷。

我們將以上代碼提交至 LeetCode，執行結果如下：

代碼實現 2：貪心改進

以上的貪心算法是一瓶酒一瓶酒進行循環兌換的，那我們可否每次將所有的空瓶子全部兌換完(可兌換的最大值)，然后將兌換的酒再喝完，再進行下一次兌換?

答案是肯定的，我們只需要使用取模和取余操作就可以實現了，具體代碼如下：

// 貪心 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/problems/water-bottles/

https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html

https://zh.wikipedia.org/zh-hans/貪心算法