编程知识 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 .

Recommended reading :

The opportunity came , Byte hopping: ten thousand people were recruited a year ago , How do we deal with the algorithms that have to be asked ?

Violence recursion algorithm explain

版权声明
本文为[Mr.Z]所创,转载请带上原文链接,感谢

Scroll to Top