In recent years, in order to stimulate consumption, businesses have launched a variety of activities in a variety of ways, and the operational e-commerce led by Some duo makes us see the infinite “potential” of marketing. This is not, just catch up with double 11 recently, the old Wang head of community convenience store also launched a “empty wine bottle for wine” promotion activity, its rules are such.

This article has been included in Github “Xiaobai Algorithms” series: github.com/vipstone/al…

Activity rules

Customers who buy X bottles of wine can exchange Y empty bottles for a new bottle.

Tip:

The values of X and Y are as follows:

  • 1 <= X <= 100
  • 2 <= Y <= 100

The Y value is not fixed. It’s random.

If you drink the wine from the bottle, it will be empty.

Please calculate the maximum number of bottles of wine you can drink.

Example 1:

Input: X = 9, Y = 3

Output: 13

Explanation: You can exchange 3 empty bottles for 1 bottle of wine. So up to 9 + 3 + 1 = 13 bottles of wine.

Example 2:

Input: X = 15, Y = 4

Output: 19

Explanation: You can exchange 4 empty bottles for 1 bottle of wine. So up to 15 + 3 + 1 = 19 bottles of wine.

Example 3:

Input: X = 5, Y = 5

Output: 6

Example 4:

Input: X = 2, Y = 3

Output: 2

Their thinking

There are two difficulties in this problem: first, the number of empty bottles for a bottle of wine is not fixed (random); Second, you can continue to participate in the exchange activities after you finish the exchange. So calculate the maximum number of bottles you can drink under these two conditions.

Some of you may know the idea after reading the title of this article, yes, we are going to use “greedy algorithm” to calculate the final answer. This problem also conforms to the greedy algorithm solution idea, that is, there is a bottle of cash, as many as you can exchange.

Greedy algorithm

The Greedy Algorithm, also known as the Greedy Algorithm, is an Algorithm that takes the best or most advantageous choice in the current state at each step in the hope that the result will be either the best or optimal.

Greedy algorithms are particularly effective in problems with optimal substructures. Optimal substructure means that the local optimal solution determines the global optimal solution. Simply put, a problem can be resolved in subproblems, and the optimal solution of the subproblem can be recurred to the optimal solution of the final problem.

Greedy algorithm implementation framework

Starting from the initial solution of the problem:

While (can make further progress towards a given general goal)

{

Using the feasible decision, a solution element of the feasible solution is obtained.

}

The combination of all the solution elements into a viable solution to the problem.

Note: because the greedy algorithm can only achieve the global optimal solution by solving the local optimal solution strategy, therefore, we must pay attention to judge whether the problem is suitable for the greedy algorithm strategy, and whether the solution is necessarily the optimal solution of the problem.

Next, we will use code to demonstrate the implementation of the greedy algorithm.

Code implementation 1: Greed

First of all, let’s convert the global problem into a local problem: when the empty bottle can be exchanged for a bottle of wine, we will change a bottle of wine, the implementation code is as follows:

// Greed 1: implement with + and -
class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        // Maximum number of bottles
        int total = numBottles;
        // If you have a bottle
        while (numBottles >= numExchange) {
            // Execute a round of exchange
            numBottles -= numExchange;
            ++total;
            // One more bottle at a time
            ++numBottles;
        }
        returntotal; }}Copy the code

Code parsing

Implementation idea:

  1. Drink all the wine firstint total = numBottles;
  2. When there are enough empty bottles, go and replace onewhileCycle;
  3. In the loop, the number of empty bottles +1, the number of bottles available +1;
  4. Perform the next loop judgment.

We submitted the above code to LeetCode and the result is as follows:

Code implementation 2: Greedy improvement

The above greedy algorithm is a bottle of wine for the cycle of exchange, so can we exchange all the empty bottles each time (the maximum value can be exchanged), and then drink the converted wine, and then the next exchange?

The answer is yes, we just need to use mod and mod operations to achieve it, the specific code is as follows:

// Greed 2: implemented with/and %
class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        // Total number of bottles
        int total = numBottles;
        // If you have a bottle
        while (numBottles >= numExchange) {
            // A maximum of new wine redeemable
            int n = numBottles / numExchange;
            // Add up the bottles
            total += n;
            // Remaining bottle (remaining unconverted + converted drunk)
            numBottles = numBottles % numExchange + n;
        }
        returntotal; }}Copy the code

We submitted the above code to LeetCode and the result is as follows:

conclusion

Greedy algorithms are “difficult” at first sight, but they are easy to implement. In fact, “algorithm” is also the same. At first glance, this word feels very difficult and lofty. In fact, it is just an idea to solve a problem, a fixed “routine”, and there is no mystery at all.

People often say: though the road is long, it will come; though the things are hard, they will be done. “Difficult” and “easy” are always relative. In fact, from “difficult” to “easy” is a process of gradual enlightenment and gradual growth.

I hope you grow up a little every day, and finally leave a private wechat account of mine: GG_Stone, for mutual communication and common progress.

Reference & acknowledgements

Leetcode-cn.com/problems/wa…

www.cnblogs.com/steven_oyj/…

Zh.wikipedia.org/zh-hans/%E8…

Follow the public account “Java Chinese Community” to see more examples of algorithms.