作者 | 王磊

來源 | Java中文社群（ID：javacn666）

轉載請聯系授權（微信ID：GG_Stone）

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

這不，最近剛趕上雙 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;} }

代碼解析

實現思路：

先把所有酒喝掉 int total = numBottles；

有足夠的空瓶就去換一瓶酒，執行一次 while?循環；

在循環中，空瓶的數量 +1，能喝到酒的數量 +1；

執行下一次循環判斷。

我們將以上代碼提交至 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/貪心算法

往期推薦

嗯，查詢滑動窗口最大值的這4種方法不錯....

小白學算法：買賣股票的最佳時機！

23張圖！萬字詳解「鏈表」，從小白到大佬！

關注我，每天陪你進步一點點！

總結

以上是生活随笔為你收集整理的双“11”搞促销？用贪心算法来盘他！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。