This post - this is a generalization of the question from here .

Suppose we have **m** divisible objects that need to be divided equally between **n** persons, and so that the total number of parts (called **N **in the text of the procedure) after cutting should be a minimum. **Cutting** procedure exactly solves this problem. It can be proved that the estimate holds **n<=N<=n+m-1**, and **N<n+m-1** if and only if there are several objects (**< m**), whose measures sum to be a multiple of the share (**Obj** in the text of the procedure).

In the attached file you can find also the text of the second procedure **Cutting1**, which is approximately solves the problem. The procedure **Cutting1** is much faster than **Cutting**. But the results of their work are usually the same or **Cutting** procedure gives a slightly better result than **Cutting1**.

Required parameters of the procedure: **L** is the list of the measures of the objects to be cutted, **n** is the number of persons. The optional parameter **Name** is a name or the list of names of the objects of** L** (if the latter then should be **nops(L)=nops(Name)** ).

**Cutting:=proc(L::list(numeric), n::posint, Name::{name,list(name)}:=Object)**

**local m, n1, L1, L11, mes, Obj, It, M, N;**

**uses combinat, ListTools;**

**m:=nops(L); L1:=sort([seq([`if`(Name::name,Name||i,Name[i]),L[i]], i=1..m)], (a,b)->a[2]<=b[2]);**

**mes:=table(map(t->t[1]=t[2],L1));**

**Obj:=`+`(L[])/n;**

**It:=proc(L1, n)**

**local i, M, m1, S, n0, a, L2;**

**if nops(L1)=1 then return [[[L1[1,1],Obj]] $ n] fi;**

**if n=1 then return [L1] fi;**

**for i from 1 while `+`(seq(L1[k,2],k=1..i))<=Obj do**

**od;**

**M:=[seq(choose(L1,k)[], k=1..ceil(nops(L1)/2))];**

**S:=[];**

**for m1 in M while nops(S)=0 do n0:=`+`(seq(m1[k,2],k=1..nops(m1)))/Obj;**

**if type(n0,integer) then S:=m1 fi;**

**od;**

**if nops(S)=0 then**

**a:=Obj-`+`(seq(L1[k,2],k=1..i-1));**

**L2:=[[L1[i,1],L1[i,2]-a],seq(L1[k],k=i+1..nops(L1))];**

** [[seq(L1[k], k=1..i-1),`if`(a=0,NULL,[L1[i,1],a])],It(L2,n-1)[]] else L2:=sort(convert(convert(L1,set) minus convert(S,set), list),(a,b)->a[2]<=b[2]);**

**[It(S,n0)[], It(L2,n-n0)[]] fi;**

**end proc;**

**M:=It(L1,n);**

**N:=add(nops(M[i]), i=1 ..nops(M));**

**Flatten(M, 1);**

**[Categorize((a,b)->a[1]=b[1],%)];**

**print(``);**

**print(cat(`Cutting scheme (total `, N, ` parts):`) );**

**print(map(t->[seq(t[k,2]/`+`(seq(t[k,2],k=1..nops(t)))*t[1,1],k=1..nops(t))], %)[]);**

**print(``);**

**print(`Scheme of sharing out:`);**

**seq([Person||k,`+`(seq(M[k,i,2]/mes[M[k,i,1]]*M[k,i,1], i=1..nops(M[k])))],k=1..n);**

**end proc:**

Examples of use.

First example from the link above:

**Cutting([225,400,625], 4, Cake);** # 3 cakes must be equally divided by 4 persons

**eval(%,[Cake1,Cake2,Cake3]=~[225,400,625]); ** # Check

Second example (the same for 10 persons):

**Cutting([225,400,625], 10, Cake);**

** **

Third example (7 identical apples should be divided between 12 persons):

**Cutting([1 $ 7], 12, apple); **

Cutting.mw

Edited:

1. Fixed a bug in the procedure **Cutting** (I forgot sort the list **L2** in sub-procedure **It** if **nops(S)<>0** ).

2. Changes made to the sub-procedure **It** for the case if there are several objects (**>1** and **< m**), whose measures sum to be a multiple of the share **Obj **.