[[351760]]

本文轉(zhuǎn)載自微信公眾號(hào)「Java中文社群」，作者磊哥。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java中文社群公眾號(hào)。   

這幾年商家為了刺激消費(fèi)是變著花樣的推出各種各樣的活動(dòng)，以某多多為首的運(yùn)營(yíng)式電商更是讓我們看到了營(yíng)銷的無(wú)限“潛力”。

這不，最近剛趕上雙 11，小區(qū)便利店的老王頭也推出了一項(xiàng)「空酒瓶子換酒」的促銷活動(dòng)，它的規(guī)則是這樣的。

本文已收錄至 Github《小白學(xué)算法》系列：https://github.com/vipstone/algorithm

活動(dòng)規(guī)則

客戶購(gòu)買 X 瓶酒，就可以用 Y 個(gè)空酒瓶來(lái)兌換一瓶新酒。

提示： 
X 和 Y 的取值如下： 
1 <= X <= 100 
2 <= Y <= 100 
Y 值不固定，隨機(jī)抽取。 

如果喝掉了酒瓶中的酒，那么酒瓶就會(huì)變成空的。

請(qǐng)你計(jì)算最多能喝到多少瓶酒。

示例 1：

輸入：X = 9, Y = 3 
輸出：13 
解釋：你可以用 3 個(gè)空酒瓶?jī)稉Q 1 瓶酒。所以最多能喝到 9 + 3 + 1 = 13 瓶酒。 

示例 2：

輸入：X = 15, Y = 4 
輸出：19 
解釋：你可以用 4 個(gè)空酒瓶?jī)稉Q 1 瓶酒。所以最多能喝到 15 + 3 + 1 = 19 瓶酒。 

示例 3：

輸入：X = 5, Y = 5 
輸出：6 

示例 4：

輸入：X = 2, Y = 3 
輸出：2 

解題思路

這道題難點(diǎn)有兩個(gè)：第一，用多少個(gè)空瓶換一瓶酒是不固定的(隨機(jī)的);第二，兌換的酒喝完之后還能繼續(xù)參與兌換活動(dòng)。因此要在滿足這兩個(gè)的前提條件下，計(jì)算自己最多能喝到幾瓶。

可能有些朋友看到了本篇標(biāo)題之后就知道了解題思路，沒(méi)錯(cuò)，我們本文就是要用「貪心算法」來(lái)計(jì)算最終答案。同時(shí)這道題也符合貪心算法的解題思路，那就是有酒瓶就兌換、能兌換多少就兌換多少。

貪心算法

貪心算法(Greedy Algorithm)，又稱貪婪算法，是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)(即最有利)的選擇，從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法。

貪心算法在有最優(yōu)子結(jié)構(gòu)的問(wèn)題中尤為有效。最優(yōu)子結(jié)構(gòu)的意思是局部最優(yōu)解能決定全局最優(yōu)解。簡(jiǎn)單地說(shuō)，問(wèn)題能夠分解成子問(wèn)題來(lái)解決，子問(wèn)題的最優(yōu)解能遞推到最終問(wèn)題的最優(yōu)解。

貪心算法的實(shí)現(xiàn)框架

從問(wèn)題的初始解出發(fā)：

while(能朝給定總目標(biāo)前進(jìn)一步)

{

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

}

由所有解元素組合成問(wèn)題的一個(gè)可行解。

注意：因?yàn)橛秘澬乃惴ㄖ荒芡ㄟ^(guò)解局部最優(yōu)解的策略來(lái)達(dá)到全局最優(yōu)解，因此，一定要注意判斷問(wèn)題是否適合采用貪心算法策略，找到的解是否一定是問(wèn)題的最優(yōu)解。

接下來(lái)我們就用代碼來(lái)演示一下貪心算法的具體實(shí)現(xiàn)。

代碼實(shí)現(xiàn) 1：貪心

首先我們先把全局問(wèn)題轉(zhuǎn)換成局部問(wèn)題：當(dāng)空瓶子能換一瓶酒的時(shí)候，我們就換一瓶酒，實(shí)現(xiàn)代碼如下：

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

代碼解析

實(shí)現(xiàn)思路：

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

我們將以上代碼提交至 LeetCode，執(zhí)行結(jié)果如下：

代碼實(shí)現(xiàn) 2：貪心改進(jìn)

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

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

// 貪心 2：用 / 和 % 實(shí)現(xiàn) 
class Solution { 
    public int numWaterBottles(int numBottles, int numExchange) { 
        // 總酒瓶數(shù) 
        int total = numBottles; 
        // 有酒瓶就兌換 
        while (numBottles >= numExchange) { 
            // 最多可兌換的新酒 
            int n = numBottles / numExchange; 
            // 累計(jì)酒瓶 
            total += n; 
            // 剩余酒瓶(剩余未兌換 + 已兌換喝掉的) 
            numBottles = numBottles % numExchange + n; 
        } 
        return total; 
    } 
} 

我們將以上代碼提交至 LeetCode，執(zhí)行結(jié)果如下：

總結(jié)

貪心算法初看感覺(jué)很“難”，但具體實(shí)現(xiàn)起來(lái)卻發(fā)現(xiàn)很簡(jiǎn)單。其實(shí)「算法」也是一樣的，初看這個(gè)詞感覺(jué)很難很高大上，其實(shí)它就是解決某個(gè)問(wèn)題的一種思想、一種固定的“套路”而已，也并無(wú)神秘可言。

人常說(shuō)：路雖遠(yuǎn)行則將至，事雖然難做者必成。“難”和“易”從來(lái)都是相對(duì)的，其實(shí)從“難”到“易”就是一個(gè)逐漸開(kāi)悟、逐漸成長(zhǎng)的過(guò)程。

愿你每天成長(zhǎng)一點(diǎn)，最后留一個(gè)我的私人微信：GG_Stone，相互交流、共同進(jìn)步。

參考 & 鳴謝

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/貪心算法