algorithm - 把N block 蛋糕分给M个人，浪费最少

Question

问题来了:

在一个聚会中有 n 个不同口味的蛋糕，每个蛋糕的体积为 V1、V2、V3 ... Vn。需要将他们分成参加聚会的 K 个人，使得

• 党的所有成员得到等量的蛋糕(假设 V，这是我们正在寻找的解决方案)

• 每位成员(member)只能获得一个单一口味的蛋糕(您不能将不同口味的蛋糕分给一个成员(member))。

• 一部分蛋糕在分发后会被浪费掉，我们要尽量减少浪费；或者，等效地，我们遵循最大分配策略

给定已知条件:如果 V 是最优解，则至少有一个蛋糕 X 可以被 V 分割而不剩下任何体积，即 Vx mod V == 0

我正在尝试寻找具有最佳时间复杂度的解决方案(蛮力可以做到，但我需要一种更快的方法)。

如有任何建议，我们将不胜感激。

谢谢

PS:不是作业，是面试题。这是暴力破解的伪代码:

int return_Max_volumn(List VolumnList)
{
    maxVolumn = 0;
    minimaxLeft = Integer.Max_value;
    for (Volumn v: VolumnList)
         for i = 1 to K people
             targeVolumn = v/i;
             NumberofpeoplecanGetcake = v1/targetVolumn + 
                 v2/targetVolumn + ... + vn/targetVolumn
             if (numberofPeopleCanGetcake >= k)
                  remainVolumn = (v1 mod targetVolumn) + (v2 mod targetVolumn)
                   + (v3 mod targetVolumn + ... + (vn mod targetVolumn)
                  if (remainVolumn < minimaxLeft)
                       update maxVolumn to be targetVolumn;
                       update minimaxLeft to be remainVolumn


     return maxVolumn
}

Answer 1

This is a somewhat classic programming-contest problem .

答案很简单:对卷 V 进行基本的二分搜索(最终答案)。

(注意标题说 M 人，但问题描述说 K。我将使用 M )

给定一个体积 V在搜索过程中，您遍历所有蛋糕，计算每个蛋糕可以用单一口味的切片(fed += floor(Vi/V))“喂饱”多少人。如果你到达 M (或'K')人们在你没有蛋糕之前“喂”，这意味着你显然也可以喂M任何音量 < V 的人通过简单地从每个蛋糕中消耗相同数量的(较小的)切片，使用完整的单一口味切片。如果你在到达 M 之前用完了蛋糕切片，这意味着你不能用任何体积喂养人们 > V要么，因为那会消耗比你已经失败的更多的蛋糕。这满足二分搜索的条件，这将引导您找到可以给 M 个人的最大量 V 单味切片。

复杂度为O(n * log((sum(Vi)/m)/eps) ) .分割:二分搜索需要 log((sum(Vi)/m)/eps) 迭代，考虑到 sum(Vi)/m 的上限每个人的蛋糕(当所有蛋糕都被完美食用时)。在每次迭代中，您最多必须通过所有 N蛋糕。 eps是您搜索的精度，应设置得足够低，不高于两个蛋糕体积之间的最小非零差除以 M*2。 ，以保证正确答案。通常您可以将其设置为绝对精度，例如 1e-6或 1e-9 .

为了加快一般情况下的速度，您应该按递减顺序对蛋糕进行排序，这样当您尝试大体积时，您会立即丢弃所有尾随的总体积 < V 的蛋糕。 (例如，你有一个体积为 10^6 的蛋糕，然后是一堆体积为 1.0 的蛋糕。如果你正在测试 2.0 的切片体积，一旦你到达第一个体积为 1.0 的蛋糕，你已经可以返回此运行未能提供 M 切片)

编辑:

搜索实际上是用 float 完成的，例如:

double mid, lo = 0, hi = sum(Vi)/people;
while(hi - lo > eps){
    mid = (lo+hi)/2;
    if(works(mid)) lo = mid;
    else hi = mid;
}
final_V = lo;

到最后，如果您真的需要比您选择的 eps 更高的精度，您可以简单地采取额外的 O(n) 步骤:

// (this step is exclusively to retrieve an exact answer from the final
// answer above, if a precision of 'eps' is not acceptable)
foreach (cake_volume vi){
   int slices = round(vi/final_V);
   double difference = abs(vi-(final_V*slices));
   if(difference < best){
       best = difference;
       volume = vi;
       denominator = slices;
   }
}
// exact answer is volume/denominator