将N饼分成最少浪费的M人

Question

所以这是一个问题:

在一个派对中,有n种不同口味的蛋糕,每卷的体积为V1,V2,V3 ...... Vn.需要将它们划分为存在于党内的K人

• 派对的所有成员获得相同数量的蛋糕(比如V,这是我们正在寻找的解决方案)

• 每个成员应该只获得一种单味的蛋糕(你不能将不同风味蛋糕的部分分配给一个成员).

• 分配后会浪费一些蛋糕,我们希望尽量减少浪费; 或者,等同于我们遵循最大分配政策

给定已知条件:如果V是最优解,那么至少一个滤饼X可以除以V而不留任何体积,即Vx mod V == 0

我正在努力寻找具有最佳时间复杂度的解决方案(蛮力会做到这一点,但我需要更快的方式).

任何建议将不胜感激.

谢谢

PS:这不是作业,而是面试问题.这是蛮力的pseducode:

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

这是一个有点经典的编程竞赛问题.

答案很简单:在卷上进行基本的二进制搜索V(最终答案).

(注意标题是M人,但问题描述说K.我将使用M)

V在搜索过程中给定一个音量时,您将遍历所有蛋糕,计算每个蛋糕可以用单味道切片"喂"多少人(fed += floor(Vi/V)).如果你M在失去蛋糕之前到达(或'K')人"喂",这意味着你可以通过简单地消耗相同数量的(较小的)来显然也可以给M任何体积的人喂食< V每个蛋糕切片.如果你在到达M切片之前用完了蛋糕,这意味着你不能给任何体积的人喂食V,因为这会消耗比你已经失败的蛋糕更多的蛋糕.这满足二进制搜索的条件,它将引导您达到最高音量V.可以给M人的单味片.

复杂性是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切片)

编辑:

搜索实际上是使用浮点数来完成的,例如:

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

Answer 2

所以这是我认为可行的算法：

1. 将体积从最大到最小排序。
2. 将最大的蛋糕分给1...k人，即target=volume[0]/i，其中i=1,2,3,4,...,k
3. 如果目标导致碎片总数大于 k，则减少 i 的数量并重试。
4. 找到第一个数字i，它会导致块的总数大于或等于 K，但(i-1)将导致蛋糕的总数小于 k。将此卷记录为基本卷。
5. 对于每个剩余的蛋糕，找到剩余体积除以人数的最小分数，即，除法 = (V_cake - (baseVolume*(Math.floor(V_cake/baseVolume)) ) / Math.floor(V_cake/baseVolume)
6. 将此数量添加到 baseVolume(baseVolume += 除法) 中，并重新计算所有卷可以分割的总块数。如果新卷导致件数减少，则返回之前的值，否则重复步骤 6。

下面是java代码：

public static int getKonLagestCake(Integer[] sortedVolumesList, int k) {
    int result = 0;
    for (int i = k; i >= 1; i--) {
        double volumeDividedByLargestCake = (double) sortedVolumesList[0]
                / i;
        int totalNumber = totalNumberofCakeWithGivenVolumn(
                sortedVolumesList, volumeDividedByLargestCake);
        if (totalNumber < k) {
                result = i + 1;
                break;
        }
    }
    return result;
}


public static int totalNumberofCakeWithGivenVolumn(
        Integer[] sortedVolumnsList, double givenVolumn) {
    int totalNumber = 0;
    for (int volume : sortedVolumnsList) {
        totalNumber += (int) (volume / givenVolumn);
    }
    return totalNumber;
}

public static double getMaxVolume(int[] volumesList, int k) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i : volumesList) {
        list.add(i);
    }

    Collections.sort(list, Collections.reverseOrder());
    Integer[] sortedVolumesList = new Integer[list.size()];
    list.toArray(sortedVolumesList);

    int previousValidK = getKonLagestCake(sortedVolumesList, k);
    double baseVolume = (double) sortedVolumesList[0] / (double) previousValidK;

    int totalNumberofCakeAvailable = totalNumberofCakeWithGivenVolumn(sortedVolumesList, baseVolume);

    if (totalNumberofCakeAvailable == k) {
        return baseVolume;
    } else {
        do
        {
            double minimumAmountAdded = minimumAmountAdded(sortedVolumesList, baseVolume);

            if(minimumAmountAdded == 0)
            {
                return baseVolume;
            }else
            {
                baseVolume += minimumAmountAdded;
                int newTotalNumber = totalNumberofCakeWithGivenVolumn(sortedVolumesList, baseVolume);

                if(newTotalNumber == k)
                {
                    return baseVolume;
                }else if (newTotalNumber < k)
                {
                    return (baseVolume - minimumAmountAdded);
                }else
                {
                    continue;
                }
            }

        }while(true);
    }

}

public static double minimumAmountAdded(Integer[] sortedVolumesList, double volume)
{
    double mimumAdded = Double.MAX_VALUE;
    for(Integer i:sortedVolumesList)
    {
        int assignedPeople = (int)(i/volume);
        if (assignedPeople == 0)
        {
            continue;
        }
        double leftPiece = (double)i - assignedPeople*volume;

        if(leftPiece == 0)
        {
            continue;
        }

        double division = leftPiece / (double)assignedPeople;
        if (division < mimumAdded)
        {
            mimumAdded = division;
        }
    }

    if (mimumAdded == Double.MAX_VALUE)
    {
        return 0;
    }else
    {
        return mimumAdded;
    }
}

任何评论将不胜感激。谢谢