漫畫：有趣的 “切蛋糕“ 問題

//剩余蛋糕數(shù)量
static int leftCakes[];
//蛋糕總量（不是數(shù)量，而是大小之和）
static int totalCake = 0;
//浪費蛋糕量
static int lostCake = 0;
static boolean canFeed(int[] mouths, int monthIndex, int sum)
{
   if(monthIndex<=0) {
       //遞歸邊界
       return true;
   }
   //如果 蛋糕總量-浪費蛋糕量 小于當前的需求量，直接返回false，即無法滿足
   if(totalCake - lostCake < sum) {
       return false;
   }
   //從小到大遍歷蛋糕
   for(int i=0;i<leftCakes.length; i++) {
       if (leftCakes[i] >= mouths[monthIndex]) {
           //找到并吃掉匹配的蛋糕
           leftCakes[i] -= mouths[monthIndex];
           //剩余蛋糕小于最小的需求，變?yōu)槔速M蛋糕
           if (leftCakes[i] < mouths[1]){
               lostCake += leftCakes[i];
           }
           //繼續(xù)遞歸，試圖滿足mid下標之前的需求
           if (canFeed(mouths, monthIndex-1, sum)) {
               return true;
           }
           //無法滿足需求，蛋糕狀態(tài)回滾
           if (leftCakes[i] < mouths[1]) {
               lostCake -= leftCakes[i];
           }
           leftCakes[i] += mouths[monthIndex];
       }
   }
   return false;
}
public static int findMaxFeed(int[] cakes, int[] mouths){
   //蛋糕升序排列，并把0下標空出
   int[] cakesTemp = Arrays.copyOf(cakes, cakes.length+1);
   Arrays.sort(cakesTemp);
   for(int cake: cakesTemp){
       totalCake += cake;
   }
   //顧客胃口升序排列，并把0下標空出
   int[] mouthsTemp = Arrays.copyOf(mouths, mouths.length+1);
   Arrays.sort(mouthsTemp);
   leftCakes = new int[cakes.length+1];
   //需求之和（下標0的元素是0個人的需求之和，下標1的元素是第1個人的需求之和，下標2的元素是第1,2個人的需求之和.....）
   int[] sum = new int[mouths.length+1];
   for(int i=1;i<=mouths.length;i++) {
       sum[i] = sum[i - 1] + mouthsTemp[i];
   }
   //left和right用于計算二分查找的“中點”
   int left=1,right=mouths.length;
   //如果胃口總量大于蛋糕總量，right指針左移
   while(sum[right]> totalCake){
       right--;
   }
   //中位指針，用于做二分查找
   int mid=((left+right)>>1);
   while(left<=right)
   {
       //重置剩余蛋糕數(shù)組
       leftCakes = Arrays.copyOf(cakesTemp, cakesTemp.length);
       //重置浪費蛋糕量
       lostCake =0;
       //遞歸尋找滿足需求的臨界點
       if(canFeed(mouthsTemp, mid, sum[mid])){
           left=mid+1;
       } else {
           right = mid - 1;
       }
       mid=((left+right)>>1);
   }
   //最終找到的是剛好滿足的臨界點
   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("最大滿足顧客數(shù)：" + maxFeed);
}

延伸閱讀??

延伸閱讀《算法導論》