## 编程知识 cdmana.com

### Double "11" promotion? This article teaches you to use greedy algorithm to disk him!

In recent years, in order to stimulate consumption, businesses have launched a variety of activities , The operational e-commerce led by a certain number of companies also let us see the infinite marketing “ potential ”.

see , Recently, I just caught up with double 11, The old Wang head of the community convenience store also launched a 「 Empty bottle for wine 」 The promotion of , Its rules are like this .

## Activity rules

Customers buy X A bottle of wine , You can use it Y An empty bottle for a new one .

Tips ：

X and Y The values of are as follows ：

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

Y The value is not fixed , Random sampling .

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

Please calculate How many bottles of wine can I drink at most .

Example 1： Input ：X = 9, Y = 3

Output ：13

explain ： You can use it. 3 An empty wine bottle 1 A bottle of wine . So you can drink at most 9 + 3 + 1 = 13 A bottle of wine .

Example 2： Input ：X = 15, Y = 4

Output ：19

explain ： You can use it. 4 An empty wine bottle 1 A bottle of wine . So you can drink at most 15 + 3 + 1 = 19 A bottle 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 of all , How many empty bottles to exchange for a bottle of wine is not fixed （ Random ）; second , After drinking the wine, you can continue to participate in the exchange activities . Therefore, under the premise of satisfying these two conditions , Calculate how many bottles you can drink at most .

Some friends may know how to solve the problem after seeing the title of this article , you 're right , We are going to use 「 Greedy Algorithm 」 To calculate the final answer . At the same time, this problem also conforms to the greedy algorithm , That is to change the wine bottle when you have it 、 Change as much as you can .

## Greedy Algorithm

Greedy Algorithm （Greedy Algorithm）, Also known as greedy algorithm , It's a choice to take the best or the best in the current state at each step of the selection （ That is, the most favorable ） The choice of , So we hope that the result is the best or the best algorithm .

The greedy algorithm is particularly effective for problems with optimal substructures . The optimal substructure means that the local optimal solution can determine the global optimal solution . In short , A problem can be solved by decomposing it into subproblems , The optimal solution of the subproblem can be recursive to the optimal solution of the final problem .

### The framework of greedy algorithm

Starting from the initial solution of the problem ：

while（ To be able to take a step towards a given overall goal ）

{

Make use of feasible decisions , Find a feasible solution element ;

}

A feasible solution of the problem is composed of all Solution elements .

Be careful ： Because the greedy algorithm can only achieve the global optimal solution through the strategy of solving the local optimal solution , therefore , Be sure to judge whether the problem is suitable for greedy algorithm strategy , Whether the solution found must be the optimal solution of the problem .

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

## Code implementation 1： greedy

First, we transform the global problem into a local problem ： When an empty bottle can be exchanged for a bottle of wine , Let's change a bottle of wine , The implementation code is as follows ：

``````//  greedy 1： use  +  and  -  Realization
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
//  Maximum number of bottles
int total = numBottles;
//  If you have a bottle, change it
while (numBottles >= numExchange) {
//  Perform a round of exchange
numBottles -= numExchange;
++total;
//  Exchange one more bottle at a time
++numBottles;
}
return total;
}
} ``````

Code parsing

Realize the idea ：

1. Drink all the wine first  `int total = numBottles`;
2. If you have enough empty bottles, change to another bottle of wine , Do it once  `while`  loop ;
3. In circulation , The number of empty bottles +1, The amount of wine you can drink +1;
4. Perform the next loop judgment .

We submit the above code to LeetCode, The results are as follows ： ## Code implementation 2： Greedy for improvement

The above greedy algorithm is a bottle of wine, a bottle of wine for circular exchange , Can we exchange all the empty bottles every time （ The maximum value of convertibility ）, Then drink the exchange wine again , Make the next exchange ？

The answer is yes , We only need to use the operation of module and remainder to achieve , The specific code is as follows ：

``````//  greedy  2： use  /  and  %  Realization
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
//  Total bottles
int total = numBottles;
//  If you have a bottle, change it
while (numBottles >= numExchange) {
//  The most convertible new wine
int n = numBottles / numExchange;
//  Cumulative bottles
total += n;
//  Remaining bottles ( The rest is not exchanged  +  Have been exchanged for drink )
numBottles = numBottles % numExchange + n;
}
return total;
}
} ``````

We submit the above code to LeetCode, The results are as follows ： ## summary

Greedy algorithm at first glance feel very “ difficult ”, But the concrete realization is very simple . Actually 「 Algorithm 」 It's the same , It's hard to be tall at first , In fact, it is an idea to solve a problem 、 A fixed “ tricks ” nothing more , There's no mystery .

People often say ： Though the road is long, it will come , Though things are hard to do, they will be done .“ difficult ” and “ easy ” It's always relative , Actually from “ difficult ” To “ easy ” It's a gradual enlightenment 、 The process of gradual growth .