Minimitzar el màxim de les sumes P23519

Donats dos naturals $m$ i $n$ i un vector $v$ d’$n$ naturals, es vol trobar quina és el mínim del màxim de les sumes dels trossos de $v$ quan aquest és tallat en $m$ trossos.

Per exemple: Considereu $m=2, n=4$ i $v=[12, 34, 67, 90]$. Hi ha tres maneres de tallar $v$ en $m$ trossos: $[12 \vert 34, 67, 90]$, $[12, 34 \vert 67, 90]$ i $[12, 34, 67 \vert 90]$. En el primer cas, el primer tros suma 12 i el segon suma 191. Per tant el màxim de les sumes és 191. Pel segon cas el màxim de les sumes és 157, i pel tercer cas el màxim de les sumes és 113. Per tant, el mínim dels màxims de les sumes és 113.

Resoleu el problema en tres passos:

1. Primer, escriviu una funció bool has_max_sum(const vector<int>& v, int m, int x) que indiqui si es pot tallar $v$ en $m$ trossos de forma que el màxim de les sumes dels trossos sigui $x$ o menys.

2. Després, escriviu una funció int min_max_sum(const vector<int>& v, int m) que retorni el mínim dels màxims de les sumes de $v$ en $m$ trossos utilitzant has_max_sum astutament.

3. Finalment, descriviu en un comentari a l’inici del programa quina és l’estratègia del vostre algorisme i quin és el seu cost.

Descarregueu el fitxer code.cc per trobar l’esquelet del codi i el comentari i la implementació del programa principal. Podeu assumir que $n\geq m\geq 1$, i que $S$, la suma dels elements del vector, cap en un int.