Divide N cake to M people with minimum wastes

Question

So here is the question:

In a party there are n different-flavored cakes of volume V1, V2, V3 ... Vn each. Need to divide them into K people present in the party such that

• All members of party get equal volume of cake (say V, which is the solution we are looking for)

• Each member should get a cake of single flavour only (you cannot distribute parts of different flavored cakes to a member).

• Some volume of cake will be wasted after distribution, we want to minimize the waste; or, equivalently, we are after a maximum distribution policy

Given known condition that: if V is an optimal solution, then at least one cake, X, can be divided by V without any volume left, i.e., Vx mod V == 0

I am trying to look for a solution with best time complexity (brute force will do it, but I need a quicker way).

Any suggestion would be appreciated.

Thanks

PS: It is not an assignment, it is an Interview question. Here is the pseducode for brute force:

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.

The answer is simple: do a basic binary search on volume V (the final answer).

(Note the title says M people, yet the problem description says K. I'll be using M)

Given a volume V during the search, you iterate through all of the cakes, calculating how many people each cake can "feed" with single-flavor slices (fed += floor(Vi/V)). If you reach M (or 'K') people "fed" before you're out of cakes, this means you can obviously also feed M people with any volume < V with whole single-flavor slices, by simply consuming the same amount of (smaller) slices from each cake. If you run out of cakes before reaching M slices, it means you cannot feed the people with any volume > V either, as that would consume even more cake than what you've already failed with. This satisfies the condition for a binary search, which will lead you to the highest volume V of single-flavor slices that can be given to M people.

The complexity is O(n * log((sum(Vi)/m)/eps) ). Breakdown: the binary search takes log((sum(Vi)/m)/eps) iterations, considering the upper bound of sum(Vi)/m cake for each person (when all the cakes get consumed perfectly). At each iteration, you have to pass through at most all N cakes. eps is the precision of your search and should be set low enough, no higher than the minimum non-zero difference between the volume of two cakes, divided by M*2, so as to guarantee a correct answer. Usually you can just set it to an absolute precision such as 1e-6 or 1e-9.

To speed things up for the average case, you should sort the cakes in decreasing order, such that when you are trying a large volume, you instantly discard all the trailing cakes with total volume < V (e.g. you have one cake of volume 10^6 followed by a bunch of cakes of volume 1.0. If you're testing a slice volume of 2.0, as soon as you reach the first cake of volume 1.0 you can already return that this run failed to provide M slices)

Edit:

The search is actually done with floating point numbers, e.g.:

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;

By the end, if you really need more precision than your chosen eps, you can simply take an extra O(n) step:

// (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

Here's the approach I would consider:

Let's assume that all of our cakes are sorted in the order of non-decreasing size, meaning that Vn is the largest cake and V1 is the smallest cake.

1. Generate the first intermediate solution by dividing only the largest cake between all k people. I.e. V = Vn / k.
2. Immediately discard all cakes that are smaller than V - any intermediate solution that involves these cakes is guaranteed to be worse than our intermediate solution from step 1. Now we are left with cakes Vb, ..., Vn, where b is greater or equal to 1.
3. If all cakes got discarded except the biggest one, then we are done. V is the solution. END.
4. Since we have more than one cake left, let's improve our intermediate solution by redistributing some of the slices to the second biggest cake Vn-1, i.e. find the biggest value of V so that floor(Vn / V) + floor(Vn-1 / V) = k. This can be done by performing a binary search between the current value of V and the upper limit (Vn + Vn-1) / k, or by something more clever.
5. Again, just like we did on step 2, immediately discard all cakes that are smaller than V - any intermediate solution that involves these cakes is guaranteed to be worse than our intermediate solution from step 4.
6. If all cakes got discarded except the two biggest ones, then we are done. V is the solution. END.
7. Continue to involve the new "big" cakes in right-to-left direction, improve the intermediate solution, and continue to discard "small" cakes in left-to-right direction until all remaining cakes get used up.

P.S. The complexity of step 4 seems to be equivalent to the complexity of the entire problem, meaning that the above can be seen as an optimization approach, but not a real solution. Oh well, for what it is worth... :)