当前位置：网站首页>Cartoon: interesting "cake cutting" problem

Cartoon: interesting "cake cutting" problem

2022-06-11 14:22:00 【Big data V】

Reading guide ： It's brain burning and interesting ACM The title of the competition .

author ： Ash

source ： Programmer Xiaohui （ID：chengxuyuanxiaohui）

————— the second day —————

for instance ：

We have 5 A piece of cake , What's the size of the cake 5,17,25,3,15

We have 7 Customers , Their appetite is 2,5,7,9,12,14,20

（ The size of each cake and the amount of food the customer eats are less than 1000 The integer of , The number of cakes and customers does not exceed 1000）

In the distribution of the cake , There is a special rule ： Cake can be divided or not .

What does that mean ？

A bigger cake , It can be cut into small pieces , To satisfy multiple customers with less appetite ：

however , Some smaller cakes , Don't allow Merge into a big cake , To satisfy a customer with a big appetite ：

The last question is ： A set of given cake sizes cakes, A set of meals for a given customer mouths, How to calculate the maximum number of customers these cakes can satisfy ？

such as ： Input cakes aggregate {2,9}; Input mouths aggregate {5,4, 2,8}
Correct return ：3

Xiao Hui's idea ：

In order to satisfy more customers , Be sure to give priority to customers with a small amount of food , So Xiaohui decided to use Greedy Algorithm .

First , Sort the cake and customers from small to large ：

Follow the example above , The results are as follows ：

Next , Let each cake match the customer from left to right . If the cake is bigger than the customer's appetite , Cut the cake ; If the cake is less than the customer's appetite , Then discard the cake .

The first 1 The size of the cake is 3, The first 1 A customer's appetite is 2, So I cut the cake into 2+1, Satisfy customers . The rest 1 Big and small cakes can't satisfy the next customer , discarded .

The first 2 The size of the cake is 5, The first 2 A customer's appetite is 5, Just to satisfy the customers .

The first 3 The size of the cake is 15, The first 3 A customer's appetite is 7, So I cut the cake into 7+8, Satisfy customers . The rest 8 Big and small cakes can't satisfy the next customer , discarded .

The first 4 The size of the cake is 17, The first 4 A customer's appetite is 9, So I cut the cake into 9+8, Satisfy customers . The rest 8 Big and small cakes can't satisfy the next customer , discarded .

The first 5 The size of the cake is 25, The first 5 A customer's appetite is 12, So I cut the cake into 12+13, Satisfy customers . The rest 13 Big and small cakes can't satisfy the next customer , discarded .

thus , All the cakes are used up , From the greedy algorithm , The maximum number of customers that can be satisfied is 5.

In the example ：

3 My cake is full of 2 Customers ,
5 My cake is full of 5 Customers ,
15 My cake is full of 12 Customers ,
17 My cake is full of 7 and 9 Customers ,
25 My cake is full of 14 Customers .

obviously , How to eat as the interviewer likes , To satisfy the 6 A customer .

————————————

This sentence sounds a bit circuitous , What does that mean ？ Let's take a look at the picture below ：

In fact, it's very simple , Because customers' appetite is ranked from small to large , Give priority to small customers , To satisfy as many people as possible .

therefore , In the array that records how much customers eat , There must be a continuous element from the far left , In line with the current cake can meet the most customer portfolio .

thus , Our topic starts with Looking for the maximum number of satisfied customers , Transformed into Find the maximum satisfaction critical point in the ordered array of customers' appetite ：

Let's review the idea of binary search ：

1. Choose the middle element , Subscript mid = （0 + 6）/2 = 3 , So the intermediate element is 9：

2. Judge 9>5, Select element 9 The middle element on the left side , Subscript mid = （0+2）/2 = 1, So the intermediate element is 5：

3. Judge 5=5, Find the end .

however , The problem of cake cutting is much more complicated than the ordinary binary search , Because we're looking for the critical element of the customer appetite array , It's not a simple matter of judging whether the elements are equal , It's about verifying that a given cake meets all the customers before the critical element .

How do you do that ？ We're still using the example , Show me the details ：

First step , Look for the middle element of the customer array .

ad locum , The middle element is 9：

The second step , Verify the appetite from 2 To 9 Whether our customers can satisfy .

substep 1, Traversing the cake array , Look for bigger than 9 The cake , Finally, we find the elements 15.

substep 2, Appetite 9 Our customers eat 15 The cake , And then there were 6 size .

substep 3, Traverse the cake array again , Look for bigger than 7 The cake , Finally, we find the elements 17.

substep 4, Appetite 7 Our customers eat 17 The cake , And then there were 10 size .

substep 5, Traverse the cake array again , Look for bigger than 5 The cake , Finally, we find the elements 5.

substep 6, Appetite 5 Our customers eat 5 The cake , And then there were 0 size .

substep 7, Traverse the cake array again , Look for bigger than 2 The cake , Finally, we find the elements 3.

substep 8, Appetite 2 Our customers eat 3 The cake , And then there were 1 size .

Only this and nothing more , from 2 To 9 All of our customers are satisfied , Verify success .

Next , We need to bring in more customers , So as to try to find out the upper limit of customers that the cake can satisfy .

The third step , Rediscover the middle element of customer array .

Because the second step is successful , So we're going to be in the element 9 The area on the right , Looking for the middle element again . obviously , This intermediate element is 14：

Step four , Verify the appetite from 2 To 14 Whether our customers can satisfy .

The idea of this step is the same as that of the second step , I won't go into details here . The final verification result is , from 2 To 14 Our customers can satisfy .

Next , We need to bring in more customers , Try to find out the upper limit of customers that cake can satisfy .

Step five , Rediscover the middle element of customer array .

Because the fourth step is successful , So we're going to be in the element 14 The area on the right , Looking for the middle element again . obviously , This intermediate element is the only element 20：

Step six , Verify the appetite from 2 To 20 Whether our customers can satisfy .

This step and the second step 、 The fourth step is the same , I won't go into details here . The final verification result is , from 2 To 20 Customers Can't Satisfy .

Go through the above steps , We found the critical point to satisfy our customers 14, from 2 To 14 share 6 A customer , therefore The maximum number of customers a given cake can satisfy is 6.

// Number of cakes left 
static int leftCakes[];
// The total amount of cake （ Not quantity , It's the sum of size ）
static int totalCake = 0;
// Waste cake quantity 
static int lostCake = 0;
static boolean canFeed(int[] mouths, int monthIndex, int sum)
{
   if(monthIndex<=0) {
       // Recursive boundary 
       return true;
   }
   // If   The total amount of cake - Waste cake quantity   Less than the current demand , Go straight back to false, That is, it can't meet 
   if(totalCake - lostCake < sum) {
       return false;
   }
   // Traverse the cake from small to large 
   for(int i=0;i<leftCakes.length; i++) {
       if (leftCakes[i] >= mouths[monthIndex]) {
           // Find and eat the matching cake 
           leftCakes[i] -= mouths[monthIndex];
           // The remaining cake is less than the minimum demand , Become a waste of cake 
           if (leftCakes[i] < mouths[1]){
               lostCake += leftCakes[i];
           }
           // Continue to recursive , Try to satisfy mid Requirements before subscribing 
           if (canFeed(mouths, monthIndex-1, sum)) {
               return true;
           }
           // Unable to meet demand , Cake state rollback 
           if (leftCakes[i] < mouths[1]) {
               lostCake -= leftCakes[i];
           }
           leftCakes[i] += mouths[monthIndex];
       }
   }
   return false;
}
public static int findMaxFeed(int[] cakes, int[] mouths){
   // The cakes are arranged in ascending order , And put 0 The subscript is empty 
   int[] cakesTemp = Arrays.copyOf(cakes, cakes.length+1);
   Arrays.sort(cakesTemp);
   for(int cake: cakesTemp){
       totalCake += cake;
   }
   // Customers' appetites are in ascending order , And put 0 The subscript is empty 
   int[] mouthsTemp = Arrays.copyOf(mouths, mouths.length+1);
   Arrays.sort(mouthsTemp);
   leftCakes = new int[cakes.length+1];
   // Sum of demands （ Subscript 0 The element is 0 The sum of individual needs , Subscript 1 The most important element is 1 The sum of individual needs , Subscript 2 The most important element is 1,2 The sum of individual needs .....）
   int[] sum = new int[mouths.length+1];
   for(int i=1;i<=mouths.length;i++) {
       sum[i] = sum[i - 1] + mouthsTemp[i];
   }
   //left and right Used to calculate binary search “ Midpoint ”
   int left=1,right=mouths.length;
   // If the total amount of appetite is greater than the total amount of cake ,right Move the pointer to the left 
   while(sum[right]> totalCake){
       right--;
   }
   // Median pointer , Used for binary search 
   int mid=((left+right)>>1);
   while(left<=right)
   {
       // Reset the remaining cake array 
       leftCakes = Arrays.copyOf(cakesTemp, cakesTemp.length);
       // Reset wasted cake quantity 
       lostCake =0;
       // Recursively find the critical point to meet the requirements 
       if(canFeed(mouthsTemp, mid, sum[mid])){
           left=mid+1;
       } else {
           right = mid - 1;
       }
       mid=((left+right)>>1);
   }
   // Finally, we find the critical point which is just satisfied 
   return mid;
}
public static void main(String[] args) {
   int[] cakes = new int[]{3,5,15,17,25};
   int[] mouths = new int[]{2,5,7,9,12,14,20};
   int maxFeed = findMaxFeed(cakes, mouths);
   System.out.println(" Maximum number of satisfied customers ：" + maxFeed);
}

This code is more complicated , A few points need to be explained ：

The mainstream method findMaxFeed, Perform various initializations , Control the binary search process .
Method canFeed, It is used to check whether the customers before a certain position can be satisfied by a given cake .
Array leftCakes, Used to temporarily store the remaining cake size , Every time you reset the middle subscript , This array needs to be reset .