沉迷算法,无法自拔。
分蛋糕问题
给定蛋糕大小的集合
如上图所示:
第1块蛋糕大小是3,第1个顾客饭量是2,于是把蛋糕切分成2+1,满足顾客。剩下的1大小蛋糕无法满足下一位顾客,丢弃掉。
第2块蛋糕大小是5,第2个顾客饭量是5,刚好满足顾客。
第3块蛋糕大小是15,第3个顾客饭量是7,于是把蛋糕切分成7+8,满足顾客。剩下的8大小蛋糕无法满足下一位顾客,丢弃掉。
第4块蛋糕大小是17,第4个顾客饭量是9,于是把蛋糕切分成9+8,满足顾客。剩下的8大小蛋糕无法满足下一位顾客,丢弃掉。
第5块蛋糕大小是25,第4个顾客饭量是12,于是把蛋糕切分成12+13,满足顾客。剩下的13大小蛋糕无法满足下一位顾客,丢弃掉。
这样一来,所有蛋糕都用完了,由贪心算法得出结论,最大能满足的顾客数量是5。
但是!再此例子中,换一种分法如下图:
3的蛋糕满足2的顾客, 5的蛋糕满足5的顾客, 15的蛋糕满足12的顾客, 17的蛋糕满足7和9的顾客, 25的蛋糕满足14的顾客。 显然,此种吃法,满足了6个顾客。
如此看来,此种分蛋糕的方式是错误的。究其原因是因为没有抓住题目的关键点:当顾客从小到大排序之后,无论蛋糕大小如何,最多能满足的顾客组合中,一定有一个组合是连续的。
其实道理很简单,由于顾客的饭量是从小到大排序的,优先满足饭量小的顾客,才能尽量满足更多的人。
因此,在记录顾客饭量的数组中,必定存在一段从最左侧开始的连续元素,符合当前蛋糕所能满足的最多顾客组合。
这样一来,我们的题目就从寻找最大满足顾客数量,转化成了寻找顾客饭量有序数组中的最大满足临界点。
而找到数组中的一个临界点,我们可以采用二分法查找
第一步,寻找顾客数组的中间元素。
第二步,验证饭量从2到9的顾客能否满足。
第三步,重新寻找顾客数组的中间元素。
第四步,验证饭量从2到14的顾客能否满足。
第五步,重新寻找顾客数组的中间元素。
第六步,验证饭量从2到20的顾客能否满足。
思路明确后,代码就呼之欲出了:
/**
* 分蛋糕问题
*/
//剩余蛋糕数量
private static int[] leftCakes;
//蛋糕总量(不是数量,而是大小之和)
private static int totalCake = 0;
//浪费蛋糕量
private static int lostCake = 0;
/**
* 子方法:检验顾客能否满足
*/
private 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];
//剩余蛋糕小于最小的需求,变为浪费蛋糕
if (leftCakes[i] < mouths[1]) {
lostCake += leftCakes[i];
}
//继续递归,试图满足mid下标之前的需求
if (canFeed(mouths, monthIndex - 1, sum)) {
return true;
}
//无法满足需求,蛋糕状态回滚
if (leftCakes[i] < mouths[1]) {
lostCake -= leftCakes[i];
}
leftCakes[i] += mouths[monthIndex];
}
}
return false;
}
/**
* 主流程方法
*
* @param cakes 蛋糕数组
* @param mouths 顾客数组
* @return 人数
*/
public 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) {
//重置剩余蛋糕数组
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;
}
代码说明:
1.主流程方法findMaxFeed,执行各种初始化,控制二分查找流程。
2.方法canFeed,用于检验某一位置之前的顾客是否能被给定蛋糕满足。
3.数组leftCakes,用于临时存储剩余的蛋糕大小,每次重新设置中间下标时,这个数组需要被重置。
4.方法canFeed,可以采用更优质的算法解决。