Databases
StackOverflow2013
Postsdbo
PODivide N cake to M people with minimum wastes
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODivide N cake to M people with minimum wastes
    primarykey
    data
    text
    <p>So here is the question:</p> <p>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 </p> <ul> <li><p>All members of party get equal volume of cake (say V, which is the solution we are looking for) </p></li> <li><p>Each member should get a cake of single flavour only (you cannot distribute parts of different flavored cakes to a member). </p></li> <li><p>Some volume of cake will be wasted after distribution, we want to minimize the waste; or, equivalently, we are after a maximum distribution policy</p></li> </ul> <p>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</p> <p>I am trying to look for a solution with best time complexity (brute force will do it, but I need a quicker way). </p> <p>Any suggestion would be appreciated.</p> <p>Thanks</p> <p>PS: It is not an assignment, it is an Interview question. Here is the pseducode for brute force:</p> <pre><code>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 &gt;= k) remainVolumn = (v1 mod targetVolumn) + (v2 mod targetVolumn) + (v3 mod targetVolumn + ... + (vn mod targetVolumn) if (remainVolumn &lt; minimaxLeft) update maxVolumn to be targetVolumn; update minimaxLeft to be remainVolumn return maxVolumn } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USKing Saber
    1. USKing Saber
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PODivide N cake to M people with minimum wastes
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PODivide N cake to M people with minimum wastes
      1. US0x90
      1. VTFavorite
    3. VO
      singulars
      1. PODivide N cake to M people with minimum wastes
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhat have you considered? Any code?
      singulars
      1. PODivide N cake to M people with minimum wastes
      1. USEric Wich
    2. COHave you tried anything? It looks like you just need somebody to do your assignment.
      singulars
      1. PODivide N cake to M people with minimum wastes
      1. USAppleshell
    3. COHave you tried to think how the "brute force" algorithm would be?
      singulars
      1. PODivide N cake to M people with minimum wastes
      1. USleonbloy
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload